Если есть 2 альгорифма, которые вычисляют один и тот же результат с различными сложностями, будет ли O (log n) всегда быстрее? Если да, объясните. Кстати, это не вопрос заданий.
O (log n) всегда быстрее O (n)
Ответ 1
Нет. Если один алгоритм работает в N/100, а другой в (log N)*100, то второй будет медленнее для меньших размеров ввода. Асимптотические сложности связаны с поведением времени работы, так как входные размеры уходят в бесконечность.
Ответ 2
Нет, это не всегда будет быстрее. НО, поскольку размер проблемы растет все больше и больше, в конечном итоге вы всегда достигнете точки, где алгоритм O (log n) будет быстрее, чем O (n).
В реальных ситуациях, как правило, точка, в которой алгоритм O (log n) обогнал бы алгоритм O (n), приходил бы очень быстро. Между O (log n) и O (n) существует большая разница, так же как большая разница между O (n) и O (n ^ 2).
Если у вас есть шанс прочитать "Программирование жемчуга" Джона Бентли, там есть удивительная глава, где он разбивает алгоритм O (n) на O (n ^ 2), делая все возможное, чтобы дать O ( п ^ 2) преимущество. (Он кодирует алгоритм O (n ^ 2) в C на альфе и алгоритм O (n) в интерпретированном BASIC на старом Z80 или что-то в нем, работающий примерно на 1 МГц). Удивительно, как быстро O (n) алгоритм обгоняет O (n ^ 2).
Иногда, однако, вы можете найти очень сложный алгоритм, который имеет сложность чуть-чуть лучше простой. В таком случае не слепо выбирайте алгоритм с лучшим большим-O - вы можете обнаружить, что он работает быстрее только при чрезвычайно больших проблемах.