Какой алгоритм лучше (и почему) с точки зрения сложности - PullRequest
Новая
       21

Какой алгоритм лучше (и почему) с точки зрения сложности

0 голосов
/ 30 сентября 2019

Предположим, есть два алгоритма, первый алгоритм имеет временную сложность O (n ^ 2), второй алгоритм имеет временную сложность O (n (log n) ^ d-2), где n - числоточек в наборе данных, а d - это число измерений. Какой из них лучше с точки зрения сложности времени. Может кто-нибудь, пожалуйста, объясните разницу в деталях.

1 Ответ

1 голос
/ 30 сентября 2019

Сложность Big-O полезна только для сравнения очень больших чисел. Другими словами, вы можете сравнить два выражения big-O, когда интересующее вас число становится огромным.

Самый простой способ сделать это - разделить два выражения и выяснить предел.

  • Если предел равен 0, знаменатель является более доминирующим и, следовательно, более медленным.
  • Если предел является бесконечным, числитель является более доминирующим и, следовательно, более медленным.
  • Если пределчто-то среднее, два сопоставимы для каждого. Один Big-O не может сказать вам, что быстрее для больших чисел.

Я буду использовать SageMath. Я предполагаю, что n - это то, что растет, а d постоянно. 

lim n->inf (n(log n)^d-2)/(n^2) = 0

Похоже, O(n^2) медленнее. Теперь предположим, что d также растет, по сравнению с n. Итак, давайте поместим d = a*n в уравнение: 

lim n->inf (n(log n)^(an)-2)/(n^2) = +inf

Теперь O(n(log n)^d-2) медленнее. Как насчет того, когда d растет, но сравнимо с log n? 

lim n->inf (n(log n)^(a log n)-2)/(n^2) = +inf

Опять же, O(n(log n)^d-2) будет медленнее.

Так что это говорит нам?

Это говорит нам о том, что до тех пор, пока число измерений ограничено, а n нет, алгоритм O(n^2) будет медленнее. Однако, как и для всех результатов big-O, это относится только к бесконечному n. Для любого ограниченного n вам придется проверить, какие из них работают лучше.

Примечания

Используемая настройка Sagemath: 

var ("a, b, n")
assume (n, 'integer')
assume (b, 'integer')
assume (n > 0)
assume (b > 0)
assume (a > 0)

Запросы: 

limit((n(log(n))^b-2)/(n^2), n=oo)
limit((n(log(n))^(a*n)-2)/(n^2), n=oo)
limit((n(log(n))^(a*log(n))-2)/(n^2), n=oo)
...