Наихудшее время выполнения с использованием нотации Big-Θ - PullRequest
Новая
       54

Наихудшее время выполнения с использованием нотации Big-Θ

0 голосов
/ 19 сентября 2018

Я понимаю, что самый внутренний для цикла это Θ (logn), а два самых внешних для цикла это Θ (n ^ 2), потому что это арифметическая сумма.Утверждение if - моя главная проблема.Кто-нибудь знает как это решить? 

int tally=0;
for (int i = 1; i < n; i ++)
{
   for (int j = i; j < n; j ++)
   {
        if (j % i == 0)
        {
            for (int k = 1; k < n; k *= 2)
            { 
                tally++;
            }
        }
   }
}

1 Ответ

0 голосов
/ 19 сентября 2018

Редактировать:
Теперь я заметил порядок петель: i до j.

В этом случае для данного i значение j отличается от i до n и (n/i) успешных условий if.

Таким образом, программа будет вызывать самый внутренний цикл 

n/1 +n/2+n/3+..+n/n

раз.Это сумма гармонического ряда , она сходится к n*ln(n)

Таким образом, внутренний цикл будет выполнен n*log^2(n) раз.

Как вы писали, два внешних цикла обеспечиваютO(n^2) сложность, поэтому общая сложность равна O(n^2 + n*log^2(n)), первый член заменяет второй, цикл, и, наконец, общая сложность является квадратичной.

int tally=0;
for (int i = 1; i < n; i ++)
{  
   // N TIMES
   for (int j = i; j < n; j ++)
   {  
     //N*N/2 TIMES
        if (j % i == 0)
        {
         //NlogN TIMES
            for (int k = 1; k < n; k *= 2)
            { 
             //N*logN*logN
                tally++;
            }
        }
   }
}

Старый ответ (неправильный)

Эта сложность связана с суммой sigma0 (n) функции (число делителей) и представлена ​​в виде последовательность A006218 ( проблема делителей Дирихле )

Мы видим, что аппроксимация суммы делителей для значений до n равна 

  n * ( log(n) + 2*gamma - 1 ) + O(sqrt(n))

, поэтому среднеечисло успешных условий if для счетчика цикла j равно ~log(j)

...