What is the fastest search algorithm for a list with names and numbers

by

Pseudo code, find last O(log N) of each name O(M).

auto it = vec.begin();
while (it != vec.end()) { // O(M)
  auto last = find_last_with_same_name(it, it->name); 
  sum += last.value;
  it++;
}

Use exponential_search for O(log N) for finding the last and therefore largest value.

For a total of O(M log N).

If M, the number of names is a constant you get O(log N), but that would need some rules lawyering.

More Related Contents:

  1. How to approach this hackerrank puzzle?
  2. In selection sort, if we have two duplicate elements, what is the behavior of the algorithm?
  3. Showing the order of growth of the function
  4. Why does this recursive quick sort program not work? [closed]
  5. Sort on a string that may contain a number
  6. Java lambdas 20 times slower than anonymous classes
  7. What would be the fastest method to test for primality in Java?
  8. Java, find intersection of two arrays
  9. Find top N elements in an Array
  10. Hash Set and Array List performances
  11. Java – Sort one array based on values of another array?
  12. What is the sorting algorithm for Java [closed]
  13. sorting integers in order lowest to highest java
  14. ‘MergeSort Algorithm’ – What’s the better implementation in JAVA? [closed]
  15. Mergesort in java
  16. Graph theory puzzle about connectivity?
  17. Efficiency of Java “Double Brace Initialization”?
  18. How to merge two sorted arrays into a sorted array? [closed]
  19. Does setting Java objects to null do anything anymore?
  20. Where do I find a standard Trie based map implementation in Java? [closed]
  21. Should I use Java’s String.format() if performance is important?
  22. Why does Collections.sort use Mergesort but Arrays.sort does not?
  23. Garbage collection behaviour for String.intern()
  24. How to check if array is already sorted
  25. Java XPath (Apache JAXP implementation) performance
  26. Most efficient way of converting String to Integer in java
  27. How to speed up Java VM (JVM) startup time?
  28. Java: how much time does an empty loop use?
  29. How do I get the intersection between two arrays as a new array?
  30. java: Arrays.sort() with lambda expression

Leave a Comment