помочь найти сложность этого алгоритма - PullRequest
Новая
       3

помочь найти сложность этого алгоритма

3 голосов
/ 27 августа 2010

Я пытаюсь найти сложность этого алгоритма: 

m=0;
i=1;
while (i<=n)
{
   i=i*2;
   for (j=1;j<=(long int)(log10(i)/log10(2));j++)
     for (k=1;k<=j;k++)
          m++;
}

Я думаю, что это O (log (n) * log (log (n)) * log (log (n))):

  • Цикл 'i' выполняется до тех пор, пока i = log (n)
  • Цикл 'j' работает до тех пор, пока log (i) означает log (log (n))
  • цикл 'k' выполняется до тех пор, пока k = j -> k = log (i) -> k = log (log (n))

, следовательно, O (log (n)* журнал (журнал (п)) * журнал (журнал (п))).

Ответы [ 2 ]

3 голосов
/ 29 августа 2010

Сложность времени - Тета (log (n) ^ 3).

Пусть T = floor (log_2 (n)). Ваш код может быть переписан как: 

  int m = 0;
  for (int i = 0; i <= T; i++)
   for (int j = 1; j <= i+1; j++)
    for (int k = 1; k <= j; k++)
     m++;

Что, очевидно, является тэтой (Т ^ 3).

Редактировать : Вот промежуточный шаг для переписывания вашего кода. Пусть a = log_2 (i). a всегда целое число, потому что я степень 2. Тогда ваш код явно эквивалентен: 

m=0;
a=0;
while (a<=log_2(n))
{
   a+=1;
   for (j=1;j<=a;j++)
     for (k=1;k<=j;k++)
          m++;
}

Другие изменения, которые я сделал, называли floor (log_2 (n)) как T, a как i и использовали цикл for вместо while.

Надеюсь, теперь все ясно.

1 голос
/ 27 августа 2010

Это домашняя работа?

Некоторые подсказки:

Я не уверен, что код делает то, что и должно быть. log10 возвращает значение с плавающей запятой, и приведение к (long int), вероятно, будет равно .9999999999. Я не думаю, что это предназначено. Возможно, строка должна выглядеть так: 

for (j=1;j<=(long int)(log10(i)/log10(2)+0.5);j++)

В этом случае вы можете переписать это как: 

m=0;
for (i=1, a=1; i<=n; i=i*2, a++)
    for (j=1; j<=a; j++)
        for (k=1; k<=j; k++)
            m++;

Следовательно, ваше предположение о сложности для петли 'j' и 'k' неверно.
(внешний цикл запускает log n раз, но i увеличивается до n, а не log n)

...