Нужна помощь в поиске сложности этого алгоритма

-1

Привет Мне нужна помощь в поиске сложности этого алгоритма. Не могли бы вы ответить на сложность линии за строкой, а не только на конечный результат?Нужна помощь в поиске сложности этого алгоритма

Алгоритм следующий:

int algorithm(int x) 
{ 
    int y = 1; 
    while (y <= x-1) 
    { 
     int z = y*2; 
     while (z <= x) 
     { 
      int w = 1; 
      while (w <= z) 
      { 
       w++; 
      } 
      z++; 
     } 
     y++; 
    } 
}

Любая помощь будет оценен по достоинству!

Благодаря

источник

2014-02-24 Juan David Ospina

звучит немного как " вы можете сделать мою домашнюю работу для меня ». Что вы знаете о сложности? Что вам трудно найти в этом коде? – Floris

Не совсем я просто пытаюсь самостоятельно изучить некоторые сложности. Пока я знаю, как найти сложность для первого цикла, но я не могу понять, как найти сложность циклов внутри первого цикла. –

OK; Какова сложность первого (внешнего) цикла? Если вы проигнорировали два внешних контура, какова сложность третьего (самого внутреннего) цикла? Если вы игнорируете сложность самого внутреннего цикла, какова сложность среднего цикла? Итак, теперь у вас есть результаты для 3 циклов - насколько сложным является композит? –

int algorithm(int x) 
{ 
    int y = 1; 
    while (y <= x-1) // <<< loop 1 
    { 
     int z = y*2; 
     while (z <= x) // <<< loop 2 
      int w = 1; 
      while (w <= z) // <<< loop 3 
      { 
       w++; 
      } 
      z++; 
     } 
     y++; 
    } 
}

Давайте разбить его.

Петля 1: вы идете вокруг (x-1) раз: мы называем это O (x). Легко.

Петля 2: Мы начинаем Z с 2*y, поэтому 2, 4, 6, ... Оттуда мы идем до x. Давайте добавим их:

sum((x-2) + (x-4) + (x-6) + ... + (x - x)) = 
x * x/2 - 2 * (1+2+3+...+x/2) = 
x * x/2 - 2 * (x/2)*(x/2+1)/2 ~ 
x * x/2 - x * x/4 = 
x * x/4 
= O(x^2)

Теперь внутренний цикл: он идет от w = 1 к w = z; поэтому он петли z раз. И мы знаем, что

z = 2, 4, 6, ... x

Таким образом, внутренний цикл добавляет что-то порядка x (х/2 ... одно и то же).

Объединение O (x) петли 3 с O (x^2) петли 2 (включающей эффект первого цикла), мы заключаем, что «алгоритм» имеет порядок x^3. Для проверки, мы можем изменить код:

#include <stdio.h> 

int algorithm(int x) 
{ 
    int c = 0; 
    int y = 1; 
    while (y <= x-1) 
    { 
     int z = y*2; 
     while (z <= x) 
     { 
      int w = 1; 
      while (w <= z) 
      { 
       c++; // count complexity 
       w++; 
      } 
      z++; 
     } 
     y++; 
    } 
    return c; 
} 

int main(void) { 
    int ii; 
    for(ii = 200; ii <= 400; ii+=10) { 
     printf("%d %d\n", ii, algorithm(ii)); 
    } 
}

Выход:

200 1338350 
210 1549030 
220 1780735 
230 2034465 
240 2311220 
250 2612000 
260 2937805 
270 3289635 
280 3668490 
290 4075370 
300 4511275 
310 4977205 
320 5474160 
330 6003140 
340 6565145 
350 7161175 
360 7792230 
370 8459310 
380 9163415 
390 9905545 
400 10686700

Заговор это на лин-журнала сюжета, вы получите довольно прямую линию.

enter image description here

Когда вы берете соотношение algorithm(400)/algorithm(300), вы получите 2,369. И когда вы принимаете (400/300)^3, ответ 2.370. Я думаю, что это достаточно близко, чтобы быть убедительным.

источник

2014-02-24 03:46:37 Floris

Большое спасибо! –

После формальных шагов (я надеюсь, что вы знакомы с Sigma Notation), вы будете иметь возможность получить точный порядок роста вашего алгоритма:

enter image description here

источник

2014-03-25 05:02:04

Нужна помощь в поиске сложности этого алгоритма

ответ

Смежные вопросы