Нет, это не всегда будет быстрее.НО, по мере того, как размер проблемы становится все больше и больше, в конечном итоге вы всегда достигнете точки, где алгоритм O (log n) быстрее, чем алгоритм O (n).
В действительностиВ мировых ситуациях обычно точка, в которой алгоритм O (log n) обгоняет алгоритм O (n), наступает очень быстро.Существует большая разница между O (log n) и O (n), так же, как существует большая разница между O (n) и O (n ^ 2).
Если у вас когда-нибудь будет возможностьпрочитайте Programming Pearls Джона Бентли, там есть потрясающая глава, где он сравнивает алгоритм O (n) с алгоритмом O (n ^ 2), делая все возможное, чтобы получить O (n ^ 2)преимущество.(Он кодирует алгоритм O (n ^ 2) в C на Alpha и алгоритм O (n) в интерпретируемом Бейсике на старом Z80 или чем-то, работающем на частоте около 1 МГц.) Удивительно, как быстро O (n)Алгоритм обгоняет O (n ^ 2).
Иногда, однако, вы можете найти очень сложный алгоритм, который по сложности немного лучше, чем более простой.В таком случае не выбирайте вслепую алгоритм с лучшим big-O - вы можете обнаружить, что он работает быстрее только при чрезвычайно больших задачах.