Вычисление временной сложности циклов с помощью примера in loops

привет, я работал с анализом итеративного решения, вот одна проблема, из-за которой я не могу рассчитать время выполнения в наихудшем случае.

void function(int n)
{
    int count = 0;
    for (int i=0; i<n; i++)
    {
        for (int j=i; j< i*i; j++)
        {
            if (j%i == 0)
            {
                for (int k=0; k<j; k++)
                    printf("*");
            }
        }
    }
}

Вот ссылка на указанную выше проблему: https://www.geeksforgeeks.org/analysis-algorithms-set-5-practice-problems/

См. задачу № 7.

Какова временная сложность вышеуказанной функции? В задаче говорят, что это O(n^5), но у меня есть некоторые сомнения по этому поводу, может кто-нибудь предоставить мне какое-нибудь математическое доказательство


algorithm asymptotic-complexity
person Thinker    schedule 13.05.2018    source источник
comment
Если вы просто хотите узнать, какова временная сложность, ответ дан чуть ниже вопроса по указанной вами ссылке. Если вы считаете, что это неправильный ответ, или у вас есть сомнения по этому поводу, прямо скажите об этом.   -  person Gaurav Singh    schedule 13.05.2018
comment
В задаче говорят, что это O(n^5), но у меня есть некоторые сомнения по этому поводу, может кто-нибудь предоставить мне математическое доказательство   -  person Thinker    schedule 13.05.2018

Ответы (2)


arrow_upward
1
arrow_downward

Во-первых, ваша программа рухнет, потому что if(j % i == 0), i и j равны 0
немного изменив ваш код

void function(int n)
{
    int count = 0;
    for (int i=1; i<n; i++) // runs O(n) times
        for (int j=i; j< i*i; j++)  
            if (j%i == 0) // runs O(i) times
            {
                for (int k=0; k<j; k++) // runs j times, whenever j is factor of i
                    //that is when j = i, j = 2i ... j = i* i
                    printf("*");
            }
}

бери пример, когда i = 5

Это означает, что общая сложность 

for (int j=5; j< 25; j++)  
     if (j%i == 0) // runs O(i) times
     {
      // runs j times when j = 5, 10, 15, 20
            for (int k=0; k<j; k++) {
                printf("*"); // runs j times when j =  5(1 + 2 + 3+ 4)
               // runs  j times which is i*i*(i*(i-1)/2) times
               // runs i^4 times
            }
     }

это означает, что общая сложность составляет O (n ^ 4)

person Dhruv Sehgal    schedule 13.05.2018
comment
Я также думаю, что это будет Большой O из n ^ 4, но я не понимаю, почему они заявили Большой O из n ^ 5, потому что все, что нам нужно рассчитать, — это время, когда последний цикл будет работать в худшем случае. - person Thinker; 13.05.2018
comment
Это действительно O(n^4), а также O(n^4) is O(n^5). Примечание: НЕ ДОВЕРЯЙТЕ GEEKSFORGEEKS ни в чем. Проблемы там не рассматриваются. - person Dhruv Sehgal; 13.05.2018
comment
да, O (n ^ 4) равно O (n ^ 5), но нам нужно вычислить точную асимптотическую границу. Хорошо, не могли бы вы указать мне какой-нибудь источник, где я могу решить еще одну проблему и найти надежные ответы? - person Thinker; 13.05.2018
comment
Я не знаю альтернативы, но здесь вы можете увидеть вопросы с похожими тегами. Пожалуйста, отметьте этот ответ как принятый, если он ответил на ваш вопрос. - person Dhruv Sehgal; 13.05.2018
comment
У меня все еще есть одно сомнение, что комбинированная сложность второго и третьего циклов равна i^4, и я могу варьироваться от 1 до n, так что общее количество будет 1^4+2^4+3^4+4^4......n ^4 правильно? и это будет текущей сложностью для общего решения, верно? - person Thinker; 13.05.2018
comment
общая сложность внутренних 2 циклов не равна n^3, потому что O(i) умножить на O(n^2) см. здесь для лучшего объяснения - person Dhruv Sehgal; 13.05.2018
comment
Ох, понял. Итак, фактическая сложность будет составлять некоторые из первых n кубов. - person Thinker; 13.05.2018

arrow_upward
-1
arrow_downward

Я думаю, что это может быть O (N ^ 5). Первый цикл for имеет диапазон до n, второй имеет n ^ 2 (с учетом наибольшего коэффициента), а последний совпадает со вторым. Таким образом, их умножение равно n^5.

person jihan1008    schedule 13.05.2018