Асимптотический анализ трех вложенных циклов for

Я хочу рассчитать тета-сложность этого вложенного цикла for:

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < j; k++) {
                // statement

Я бы сказал, что это n ^ 3, но я не думаю, что это правильно, потому что каждый цикл for не переходит от 1 к n. Я сделал несколько тестов:

n = 5 -> 10

10 -> 120

30 -> 4060

50 -> 19600

Так что это должно быть между n ^ 2 и n ^ 3. Я попробовал формулу суммирования и тому подобное, но мои результаты слишком высоки. Хоть и n^2 log(n), но это тоже неправильно...


complexity-theory big-theta asymptotic-complexity
person Aaron    schedule 24.02.2013    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Это O(N^3). Точная формула: (N*(N+1)*(N+2))/6

person Sergey Kalinichenko    schedule 24.02.2013
comment
@ Аарон, я спросил Wolfram Alpha (см. ссылку в ответе), он хорош в таких расчетах. - person Sergey Kalinichenko; 24.02.2013
comment
Да, я видел это, но я хочу понять, почему именно эта формула. - person Aaron; 24.02.2013
comment
Я думаю, что реальная формула n * (n-1) * (n-2) / 6. См. этот рабочий пример. В любом случае, это не меняет того факта, что это O(N^3) - person Cristian Lupascu; 24.02.2013
comment
также +1 за ссылку на Wolfram Alpha; отличный сайт - person Cristian Lupascu; 24.02.2013
comment
@w0lf Забавно, я только что обнаружил то же самое, используя похожую программу :) Я пытаюсь понять, что дает ... - person Sergey Kalinichenko; 24.02.2013
comment
Спасибо w0lf, полностью совпадает с моими тестами! Хотите объяснить, как вы его получили? - person Aaron; 24.02.2013
comment
@ Аарон, я просто взял формулу dasblinkenlight и пробовал варианты, пока не нашел работающую. У меня нет объяснения этому результату. - person Cristian Lupascu; 24.02.2013
comment
@w0lf Я думаю, что причина несоответствия та же, что и в этом тесте, основанном на вашей программе, где сумма арифметической последовательности получается как (N*(N-1))/2, а не хорошо известная (N*(N+1))/2. Проблема в том, что циклы не начинают считаться, пока i не дойдет до 2 (или до 1 в случае двух вложенных циклов), что означает, что математическое N в вашей программе (или N-1 в моей модификации вашей программы) равно N-2. Как только вы переназначите N->N-2, N+1 станет N-1, а N+2 станет N для вашей окончательной формулы. - person Sergey Kalinichenko; 24.02.2013
comment
@Aaron Формулу арифметического ряда для N*(N+1)/2 легко доказать, но формулу для SUM(x*(x+1)/2, x from 0 to N) не так просто. Зная ответ, вы, вероятно, сможете доказать его по индукции. Я уверен, что если вы спросите на сайте вопросов и ответов по математике, вы получите гораздо лучший ответ о том, как придумать эту формулу. . - person Sergey Kalinichenko; 24.02.2013
comment
Вот так; Я заметил, что изменение условий < на <= во внутренних циклах дает правильный счет на основе известной формулы. Я изменил программу и сделал версии для два и три цикла. - person Cristian Lupascu; 24.02.2013
comment
@dasblinkenlight, w0lf Это немного забавно, потому что вы, ребята, модифицировали код, чтобы он соответствовал времени выполнения ... вместо того, чтобы находить время выполнения кода :). Причина, по которой этот код не работает, заключается в том, что границы итераторов неверны для традиционного суммирования. n*(n+1)/2 - это сумма 1 + 2 + ... + n, а не 0 + 1 + ... + n-1 (что и делает код в OP и в комментариях). Если бы для написания простой математической суммы на языке требовался специальный регистр, я бы не поверил человеку, который его разработал, ха-ха (кто-то, кто ненавидит математику, но любит разрабатывать языки программирования??) - person rliu; 10.09.2013

arrow_upward
4
arrow_downward

Использование сигма-нотации — это эффективная пошаговая методология:

введите здесь описание изображения

person Mohamed Ennahdi El Idrissi    schedule 01.05.2014