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

Question

[UID_B Nintendo]

Тема: оценка сложности алгоритмов. Почему n^3 быстрей работает чем 2^n ?

Comments

[Евгений]

Sha644, и что этот кусок графика показывает?) На промежутке от ~1.5 до 8 график n^3 выше, чем 2^n; получается, наоборот быстрее «работает» 2^n, ибо медленнее растёт. В точке 8(по оси Х) графики снова пересекутся, и затем выше уже окажется 2^n

Answer 1

[Руслан .]

Потому что если подставить в формулу N >= 10, то значение 2^N больше N^3.

Comments

[GavriKos]

Да просто можно построить два графика в одной системе координат и увидеть.

Answer 2

[Mercury13]

Одно из двух.
А. O(n³) и O(2ⁿ) — сложность каких-то алгоритмов.

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

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

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

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

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

UPD. Что значит «в общем случае»? Оценку могут увеличить различные второстепенные алгоритмы вроде выделения памяти и преобразования в десятичный вид, и уменьшить — то, что 2ⁿ можно вычислть сдвигом. Не забудьте, что сложность алгоритмов определяется при n→∞.

Answer 3

[res2001]

Если рассуждать прямолинейно, то N^3 требует 3 операции умножения (O(3)) для любых N.
При этом если N > 3, то 2^N будет требовать >3 операций умножения (N операций умножения, если делать совсем уж тупо).

Но если N - целое и 2^N реализовывать сдвигом, а не умножением, то работать будет ооочень быстро - O(1) для всех N в допустимом диапазоне.

Comments

[UID_B Nintendo]

Хотел бы кое что уточнить: получается при N^3, у меня количество N элементов, точнее на каждый N-ый элемент будет уходить по 3 операции умножения. А при 2^N у меня на каждые 2 элемента будет уходить N-ое количество операций умножения. Я правильно понял ?

[res2001]

UID_B Nintendo, Я ошибся в ответе. Конечно, при N^3 - 2 операции умножения, а при 2^N - (N-1) - операций умножения.
Для 2^N - сложность O(N-1) будет для самой прямолинейной реализации. Стоит лишь чуть оптимизировать и сложность будет O(log(N)) (см. ответ Mercury13 )

Что значит "на каждые 2 элемента"? 2 элемента чего?
Для N^3 - на вычисление будет уходить 2 операции умножения.
Для 2^N - на вычисление будет уходить N-1 операций умножения.
Все просто - разложите вычисление степени в произведение и посчитайте количество операций умножения.
Если вам нужно вычислить степени для каждого элемента массива, то для каждого элемента потребуется столько операций умножения.

Answer 4

[Евгений]

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

В случае n^3 и 2^n так и получается: тыц