Почему мы используем обозначения asymptoti c (таким образом, игнорируя коэффициенты), когда говорим о временной сложности?

Question

Этот вопрос отличается от вопроса «Почему мы игнорируем коэффициенты в нотации Big-O».

При измерении временной сложности мы обычно используем нотации Big-O, которые игнорируют коэффициенты и недоминантные элементы. Однако разве инструкции 2N + C и N + C не приводят к значительным различиям во времени выполнения, особенно когда размер проблемы становится очень большим? Первый займет в два раза больше времени, чем второй, что может составить две недели по сравнению с одной неделей в реальных крупномасштабных вычислениях.

Примеры включают быструю сортировку по сравнению с другими алгоритмами сортировки O (NlogN) и тривиальным O (N ^ 3) матричное умножение по сравнению с алгоритмом Штрассена (который может быть медленнее, потому что ведущий коэффициент намного больше даже с меньшим показателем)

Answer 1

Мы используем обозначение asymptoti c, чтобы можно было говорить об эффективности алгоритмов , а не об эффективности конкретных c компьютеров.

Если вы пишете программу, которая принимает f ( n) секунд для запуска на вашем компьютере ...

Та же программа может занять f (n) / 10 секунд на гораздо более быстрой машине, но это все равно O (f (n)).

Одна и та же программа может занять f (n) * 10 секунд на гораздо более медленной машине, но это все равно O (f (n)).

На некоторых машинах может быть другое оборудование, поэтому, скажем, она быстрее , математика с плавающей запятой, но медленнее при доступе к памяти. Время, необходимое для запуска вашей программы на этой машине, может быть быстрее или медленнее, в зависимости от указанного c ввода, но по-прежнему будет O (f (n)).

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

Answer 2

Короче: потому что это слишком сложно.

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

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

Answer 3

Потому что нотация big-O сообщает вам о производительности алгоритма независимо от используемого языка, компилятора / интерпретатора или платформы. Вопреки распространенному мнению, big-O не предсказывает время выполнения. Вместо этого он сообщает вам, как алгоритм масштабирует с вводом. Сколько бы времени ни потребовалось для ввода заданного размера, алгоритм со сложностью O (n ² ) асимптотически займет в 4 раза больше времени, если вы удвоите размер ввода, и в 100 раз дольше, если вы увеличите ввод с коэффициентом 10, et c., независимо от вашего выбора языков, компиляторов или платформ.