Время выполнения вложенного цикла for

Question

1a.) Цикл находится ниже, и я хочу найти его время выполнения. Вот петля

sum = 0
for (int i =0; i < N; i++){
    for(int j = i; j >= 0; j--)
          sum ++

Первый цикл for выполняется в O (n), что легко, однако для второго я думаю, что он также выполняется за O (n), потому что всякий раз, когда j = i, этот цикл запускается i раз.

Итак, я записал, что время работы O (n ^ 2).

1b. ) Кроме того, может ли кто-нибудь также объяснить, что имеется в виду, когда проблема требует «тета-привязки»?

Answer 1

Ну, здесь довольно просто определить точное количество итераций цикла.Вы получаете 1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + N.

Это сумма N (N + 1) / 2, так что да, алгоритмическая сложность O (N) ² ).

Не могу сказать, что наткнулся на границы тэты ... на странице Википедии в нотации big-O упоминается, хотяможет быть разумным начальным пунктом.

Answer 2

Тэта-граница означает, что это жесткая асимптотическая граница, которая ограничивает время выполнения как сверху, так и снизу. В вашем примере N ^ 2 - это нижняя и верхняя границы времени выполнения, и, следовательно, это тета-граница времени выполнения.

Более формально:

существует k1 и k2 такие, что:

N ^ 2 * k1 <= N (N + 1) / 2 <= N ^ 2 * k2 </p>

для N> некоторое значение N0.

Ps. Эта книга дает довольно хорошее объяснение различных асимптотических оценок: http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1295777605&sr=8-1

Answer 3

f(n) = O(g(n)) тогда и только тогда, когда для достаточно большого n существует постоянная c такая, что f(n) <= c*g(n).По сути, запись big-O дает вам верхнюю границу.С таким же успехом можно сказать, что ваша программа работает в O(n^3), O(n^2011) и даже O(n^42142342), но это не очень поможет вам, не так ли?

Тета-запись дает вам туго привязан, что намного полезнее.f(n) = Theta(g(n)) тогда и только тогда, когда для достаточно большого значения n существуют константы c1, c2, такие что c1*g(n) <= f(n) <= c2*g(n), что означает, что вы знаете точную функцию, пропорциональную вашему алгоритму.

Ваш алгоритм 1 + 2 + 3 + ... + N операции, которые суммируются до N(N+1)/2.Это Theta(N^2), потому что N^2/4 + N/4 <= N^2/2 + N/2 <= N^2 + N.Таким образом, вы можете принять c1 и c2 в вышеприведенном определении как 1/2 и 2.

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