kostyamega8
@kostyamega8
Новичок

Почему n^3 работает быстрей чем 2^n?

Тема: оценка сложности алгоритмов. Почему n^3 быстрей работает чем 2^n ?
  • Вопрос задан
  • 1086 просмотров
Пригласить эксперта
Ответы на вопрос 4
LaRN
@LaRN
Senior Developer
Потому что если подставить в формулу N >= 10, то значение 2^N больше N^3.
Ответ написан
@Mercury13
Программист на «си с крестами» и не только
Одно из двух.
А. O(n³) и O(2n) — сложность каких-то алгоритмов.

Читайте определение символов Ландау, и будет всё понятно.
n³ = o(2n) при n→∞, что означает:

lim{n→∞} n³ / 2n = 0.

Что означает: при безграничном повышении n алгоритм, работающий за n³, будет иметь всё большее и большее преимущество перед конкурентом.

Б. n³ и 2n — функции, которые нам надо вычислить.

Сложность первой O(1) (всегда два умножения), сложность второй в общем случае — O(log n) (из-за того, что логарифмы от разных оснований отличаются на константу, а константу символы Ландау не учитывают, основание логарифма не пишут).

UPD. Что значит «в общем случае»? Оценку могут увеличить различные второстепенные алгоритмы вроде выделения памяти и преобразования в десятичный вид, и уменьшить — то, что 2n можно вычислть сдвигом. Не забудьте, что сложность алгоритмов определяется при n→∞.
Ответ написан
Комментировать
@res2001
Developer, ex-admin
Если рассуждать прямолинейно, то N^3 требует 3 операции умножения (O(3)) для любых N.
При этом если N > 3, то 2^N будет требовать >3 операций умножения (N операций умножения, если делать совсем уж тупо).

Но если N - целое и 2^N реализовывать сдвигом, а не умножением, то работать будет ооочень быстро - O(1) для всех N в допустимом диапазоне.
Ответ написан
Ответом на вопрос может послужить расчет предела отношений двух функций. Если мы утверждаем, что одна "растет" быстрее другой, то берем их отношение и считаем его предел (при n->∞). Если значение устремится к бесконечности - утверждение верно.

В случае n^3 и 2^n так и получается: тыц
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы