Почему порядок алгоритма обычно более важен, чем скорость процессора?

Ответ 1

Типичный персональный компьютер может выполнять 10^8 calculations per second.
И самый быстрый в мире суперкомпьютер 10^16 calculations per second.

Итак, предположим, что у вас на вашем ноутбуке/настольном компьютере был алгоритм O (n). И алгоритм O (n ^ 2), работающий на самом быстром суперкомпьютере мира одновременно. И если n = 10 ^ 10,

Время работы на ПК = 10 ^ 10/10 ^ 8 = 100 seconds.
Время работы на суперкомпьютере = 10 ^ 20/10 ^ 16 = 10000 seconds.

Таким образом, ноутбук превосходит суперкомпьютер огромным запасом. И в 100 раз быстрее, используя только лучший алгоритм.

Другая причина, по которой мы ищем лучшие алгоритмы, - проблема scalability. Согласно закону moore, вычислительная мощность удваивается каждые 18 месяцев. Таким образом, даже если суперкомпьютер сегодня может справиться с огромными затратами, он может оказаться неспособным сделать это некоторое время спустя, когда размер проблемы увеличился во много раз, в то время как вычислительная мощность удвоится только в течение следующих 18 месяцев.

Ответ 2

Посмотрим на пример:

У вас есть алгоритм с порядком O (n ^ 3). Вы выполняете этот алгоритм на процессоре, который может обрабатывать n = 10 за 100 миллисекунд.

Если n идет до 10000, для этого процессора потребуется 1158 дней.

Получение процессора вдвое быстрее приведет к сокращению до 579 дней.

Даже если вы смогли получить процессор в десять раз быстрее, все равно потребуется несколько месяцев.

Но заменив этот алгоритм на один из порядка O (n ^ 2) и запустив его на исходном процессоре, сократится время до 2,8 часа.

Ответ 3

нельзя сказать, что порядок алгоритма более/менее важен, чем скорость процессора!!! они не сопоставимы!!!! мы используем заказы для сравнения разных алгоритмов друг с другом, потому что мы не знаем целевую архитектуру, в которой будет выполняться алгоритм. как другое примечание, время выполнения программы зависит от многих факторов, таких как частота пропусков кэша, патч памяти основной памяти и т.д., поэтому в каждой исполняемой программе время выполнения может отличаться от предыдущих. в результате мы не можем сравнивать две программы, даже выполняя их по структуре!!!

Ответ 4

Будет ли это более важно, зависит от ситуации. Порядок сложности алгоритма напрямую не связан с его скоростью, могут быть "худшие" алгоритмы, которые решают конкретный экземпляр проблемы быстрее, чем "лучший" алгоритм. Как объясняют другие ответы, порядок сложности сводится к вопросу "Как растет потребление памяти/времени с размером ввода?". Для небольших входов вам все равно. Для средних входов вы сравниваете свои алгоритмы и смотрите, какой из них быстрее работает на вашем оборудовании. Проблема состоит в том, что неожиданно большие входы: теперь вы заботитесь о десятикратных данных десятикратного времени хруста, стократного времени ожидания или бесконечных вычислений до жары смерти Вселенной.

Наглядным примером этого является механизм обновления Windows XP. Они обрабатывают список установленных обновлений, используя алгоритм с экспоненциальным временем выполнения. Это не было проблемой и проходило приемлемо быстро, до тех пор, пока - спустя десятилетия - количество обновлений сделало это реальной проблемой.

Но как ученый-компьютер, у меня есть другое мнение, чтобы поделиться тем, что более важно: Более сложная алгоритмическая сложность. Выявление алгоритма с лучшей сложностью - это интеллектуальная проблема. Если вы только заботитесь о более быстрых результатах, вы можете так же легко обновить свое оборудование. Вы можете получить вычислительную мощность за деньги. Скорость процессоров более или менее улучшается - просто получите их, и вы тривиально ускорили свою программу ^[1]. Пока вы не достигли края (технологии или бюджета), и вам нужен лучший алгоритм. Тогда у вас есть гайка, чтобы взломать. Дразнящий мозг. Это чистое удовольствие!

_{1: Я не говорю, что быстрые процессоры тривиальны. Но использование их для решения проблем: -)}

Ответ 5

Попробуйте объяснить простым способом.
Скорость процессора измеряется в единицах циклов/сек и будет варьироваться от процессора к процессору. Чтобы судить о алго, нам нужна метрика, независимая от этого и основанная исключительно на алго.

Скажем, что для одной операции в алгоритме требуется один процессорный цикл. Итак, для порядка algo n, если вход имеет размер n, требуется n циклов процессора. Если порядок равен n ^ 2, если размер ввода равен n, требуются n ^ 2 процессорных цикла.

Итак, вы видите, что порядок алгоритма является метрикой, не зависящей от скорости процессора. Чем ниже порядок, тем быстрее он работает.
Это очень общий ответ, но я надеюсь, что он очистит ваши сомнения.