5
Предположим, что у меня есть два алгоритма A() и B() таким образом, что алгоритм A() занимает ровно O(3n^2) в то время как алгоритм B() занимает O(n^2). Хотя оба алгоритма работают в квадратичное время, можно сказать, что алгоритм B работает быстрее, чем?Когда мы должны рассмотреть константы времени работы
Я понимаю, что мы игнорируем константы при анализе времени работы алгоритма, но я хочу спросить об этом случае, когда нам нужно учитывать константы при анализе алгоритмов.
Спасибо
«точно O (3n^2)», возможно, вы имеете в виду «ровно 3n^2 шага (используя конкретную реализацию на конкретном типе компьютера, который нас интересует)»? Если каждый шаг реализованной программы, запущенной на этом компьютере, занимает такое же количество времени (например, поскольку каждый шаг имеет тот же тип), то при n> = 1 алгоритм 3n^2-шага всегда будет медленнее, чем n^2-шаговый алгоритм * с использованием этих реализаций на этом компьютере *. Но многие из этих допущений не работают на практике: например, для алгоритма часто требуются шаги «сравнения» и «своп», и это может занять разные времена. –
На любом современном компьютере даже шаги одного и того же базового типа могут занимать разные промежутки времени - например, шаг «копировать этот байт в этот байт» будет быстрее, если некоторые из его операндов окажутся в кеше. Либо вы можете включать такие детали в вашу модель, либо нет; если вы это сделаете, вы получите более точные выводы (на компьютерах, которые соответствуют модели), но меньше * общих * выводов (они не будут применяться к другим моделям). Границы наихудшего случая Big-O близки к самому общему концу спектра: при достаточно больших затратах они дают правильные выводы для * любого * компьютера. –