Мой учитель утверждал, что этот блок кода выполняется за O (n) время ... почему? - PullRequest
Новая
       11

Мой учитель утверждал, что этот блок кода выполняется за O (n) время ... почему?

3 голосов
/ 12 мая 2019

Мой учитель утверждал, что выполнение этого блока кода займет O (n) времени. Я пытаюсь понять, почему. Я понимаю, что два цикла for, связанные вместе, были бы арифметическим рядом ..... мой логический подход был, если K = 3, тогда внутренний цикл будет выполняться три раза, затем два раза, а затем один раз. Если K = 2, то внутренний цикл будет выполняться дважды, один раз, а затем остановится.

В математических терминах это будет N, N-1, N-2 для k = 3

Позже я смог использовать формулу арифметического ряда и получил N * (N + (N- (N-1)) / 2 ..

Я не знаю, как подойти к циклу while.

Все, что я могу предположить, это то, что когда N = 4, цикл запускается дважды, а до N = 9 цикл запускается трижды ... Как бы это установить математически?

Конечным результатом является N * (N + (N- (N-1))) / 2 + O (в то время как цикл), чтобы получить O (N)?

Любой совет будет принят с благодарностью. 

void doit(int n) {
     int k = 0; int m = n; int s = 0;
     while (m <= n) {
         k = k + 1;
         m = k * k;
     }

     for (int i = 0; i < k; i++) {
         for (int j = i; j < k; j++) {
             s = s + m;
             m = m - 1;
         }
     }
 }

Ответы [ 2 ]

5 голосов
/ 12 мая 2019

Сам цикл равен O(k^2), но дело в том, что предшествует ему.Цикл while находит наименьшее квадратное число m = k^2, которое больше n, поэтому в основном потому, что m относится к n, конечный результат становится практически O(n).

1 голос

Как видите, цикл while и вложенный цикл for отделены друг от друга. Поэтому мы рассчитаем сложность времени для каждого отдельно.

В то время как цикл

Внутри цикла while у нас есть инструкции, которые не зависят от n. Проблема здесь в том, как мы вычисляем количество раз выполнения цикла while. Если мы немного «обманем» и посмотрим на это с точки зрения k вместо n, мы заметим, что сразу же мы выходим из цикла, k содержит количество выполненных циклов. Это действительно похоже на счетчик. В этот момент k^2 примерно равен n, поэтому сложность составляет O(sqrt(n))

для циклов

Вот где происходит настоящее волшебство, поскольку эта часть O(n) преодолевает сложность O(sqrt(n)) цикла while.

Время, затрачиваемое каждым циклом for, можно рассматривать как сумму постоянного числа инструкций. Поэтому у нас будет вложенная сумма. Я постараюсь описать это для вас, так как StackOverflow не позволяет мне публиковать изображения. Обычно у вас есть две суммы, одна из которых начинается с i=0 и продолжается до (k-1), а другая начинается с j=1 и продолжается до (k-1), и все, что вы добавляете, - это постоянное число c команд.

Вы можете легко вычислить эту сумму, и получается, что сложность составляет O(k^2), но опять же мы должны думать в терминах n и точно так же, как прежде, чем она станет O(n).

...