* Помощь * Определение времени выполнения программы - PullRequest
Новая
       17

* Помощь * Определение времени выполнения программы

0 голосов
/ 21 июня 2019

Необходимо определить время выполнения следующего кода. Для следующего фрагмента программы приведем анализ времени выполнения Big-O.

Я попытался добавить числа к переменной, чтобы увидеть, сколько времени она займет и как ее упростить. Возникли трудности с частью I * I. Я понимаю, что второй цикл будет выполняться O (n) раз, но изо всех сил пытаюсь понять второй. Я знаю, что он будет проходить через (i ^ 2) время, давая ему время выполнения (i ^ 2), но делает ли это, что целые программы работают время n + (n ^ 2) или из-за упрощения, потому что я просто сохраняю высокий порядок Количество (N ^ 2) или я совершенно не прав, и я должен е по-разному. Я полагаю, что замедление t, if Statement и t ++ - это O (1) и они могут пренебречь.

Подводя итог, я думаю, что я путаю меня с тем, как мне следует обращаться с ними и как (i ^ 2) следует обращаться в общем времени выполнения. Поскольку я знаю, что встроенные циклы for имеют типичное время O (n ^ 2). 

int t = 0;                       //O(1)
for(int i=1; i <= n; i++)        //O(n)
   for(int j=1; j <= i*i; j++)   //O(i^2) 
      if(j % i == 0)             //O(1)
          t++;                   //O(1)

1 Ответ

0 голосов
/ 21 июня 2019

Вы правы, что типичные вложенные циклы имеют время O(N^2). Вероятно, они выглядят примерно так 

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        ...

Или какой-то вариант.

Поскольку мы их вкладываем, мы умножаем их сложности. O (N) * O (N) = O (N ^ 2).

Ваша функция немного отличается, поскольку внутренний цикл равен O (N ^ 2), как вы правильно определили, поскольку мы возводим в квадрат значение n, а затем повторяем это много раз, а внешний цикл является стандартным O (N ) петля.

O (N) * O (N ^ 2) = O (N ^ 3), что является сложностью вашей общей функции.

...