Почему программист предпочел бы O (N ^ 3) вместо O (N ^ 2)

Я учился на выпускном экзамене, и в архиве есть вопрос, что я не могу найти его ответ:

Порядком роста времени работы одного алгоритма является O (N ^ 2); порядок роста времени работы второго алгоритма равен O (N ^ 3). Список три убедительные (логичные, убедительные) причины, по которым программист предпочитают использовать алгоритм O (N ^ 3) вместо O (N ^ 2).

Ответы

Ответ 1

Я могу думать о следующих трех причинах:

  • Простота начальной реализации.
  • Простота обслуживания в будущем.
  • Алгоритм O (N ^ 3) может иметь более низкую пространственную сложность, чем алгоритм O (N ^ 2) (т.е. использует меньше памяти).

Ответ 2

Вероятно, причина № 1: потому что алгоритм O (N 2) имеет достаточно высокие константы, которые для размера рассматриваемой задачи O (N 3), версия быстрее.

Ответ 3

Вот примеры, чтобы убедить вас, что O (N³) может быть в некоторых случаях лучше, чем O (N²).

  • Алгоритм O (N²) очень сложный для кода, тогда как если размер ввода равен N ≤ 100, то для практического использования O (N³) может быть достаточно быстрым

  • O (N²) имеет большую константу, умноженную на нее, например, c = 1000, следовательно, для N = 100, c⋅N² = 1000⋅100² = 10⁷, тогда как если c = 1 для O (N3), затем c⋅N³ = 10⁶

  • Алгоритм O (N²) имеет очень большую пространственную сложность по сравнению с O (N³)

Ответ 4

Другое дело, некоторые алгоритмы имеют большой постоянный коэффициент. a O (N^2) может иметь большой постоянный коэффициент, который не сделает его действительно практичным для использования (если N достаточно мал, как любезно отмечено Торбаном)

Ответ 5

Единственная причина выбора одного алгоритма - не порядок роста времени работы. Вы должны проанализировать:

  • Как легко реализовать
  • Требуемое пространство
  • Насколько велики входы реальной жизни (иногда разница во времени наблюдается только для размеров ввода, которые никогда не происходят в действительности).

Ответ 6

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

Ответ 7

Big-O - верхняя граница в худшем случае. QuickSort - это время O (n ^ 2), а MergeSort - время O (n lgn). Но люди используют QuickSort, потому что в среднем это O (n lgn) с более низкими константами, чем MergseSort.