Блог

 function    (n)
input : an  integer n
r ← 0
for i = 1 to n  //runs n times
    for j = i     1 to n     // runs n^2 times
           for k = i   j − 1 to n   //runs n^3 times
                r ← r   1
return r
  

Мой ответ был O (n ^ 3), но когда я попытался найти его с помощью сигма-нотации, он всегда заканчивался O (n ^ 2).

Оригинальный вопрос:

Какое значение возвращается следующим алгоритмом? Какова его основная операция?
Сколько раз выполняется базовая операция? Укажите наихудшее время выполнения
алгоритма с использованием обозначения Big Oh.

tldr: алгоритм O(n^3) включен.

Почему?

Подсчитайте, как часто r <- r 1 выполняется.

Если это поможет, реализуйте его на каком-либо языке и выполните, чтобы лучше понять это. Например, в Java:

 int n = 10;

int r = 0;
for (int i = 1; i <= n; i  ) {
    for (int j = i   1; j <= n; j  ) {
        for (int k = i   j - 1; k <= n; k  ) {
            r  ;
        }
    }
}
  

Введение

Внешний цикл генерирует n итерации, правильно. Затем второй цикл будет генерировать n - 1, n - 2, n - 3, n - 4, ... поколения.

Однако самый внутренний цикл зависит от i , j и n .

Пример, исправьте i = 1 и j запустите от n - 1 до 1 . Вы доберетесь k 1 (n - 1) до n того, что вообще не выполняется. Затем 1 (n - 2) , к n которым относятся 2 прогоны, вплоть до n прогонов.

Так что с i = 1 вами получится k = 2, 3, 4, ..., n . Тогда i = 2 и вы получите k = 4, ..., n (n 1) . Это повторяется и суммируется до тех пор, пока i = n не даст только k = (n (n-2)) , в общей сложности:

 i = 1 -> k = 2, 3, 4, 5, 6, ..., n
i = 2 -> k =       4, 5, 6, ..., n, (n 1)
i = 3 -> k =             6, ..., n, (n 1), (n 2)
  .
  .
  .
i = n -> k =                  (n (n-2))
  

Для примера с n = 10 этим:

 2, 3, 4, 5, 6, 7, 8, 9, 10 
      4, 5, 6, 7, 8, 9, 10, 11
            6, 7, 8, 9, 10, 11, 12
                  8, 9, 10, 11, 12, 13
                        10, 11, 12, 13, 14
                                12, 13, 14, 15
                                        14, 15, 16
                                                16, 17
                                                        18
  

для k .

Значения для k

Теперь обратите внимание, что цикл выполняется только до k <= n . Таким образом, вы можете отбросить все значения k выше n и подсчитать итерации для оставшихся значений.

 2, 3, 4, 5, 6, 7, 8, 9, 10| 
      4, 5, 6, 7, 8, 9, 10|, 11
            6, 7, 8, 9, 10|, 11, 12
                  8, 9, 10|, 11, 12, 13
                        10|, 11, 12, 13, 14
                          |     12, 13, 14, 15
                          |             14, 15, 16
                          |                    16, 17
                          |                           18
  

Общее количество запусков

Таким образом, каждый из них является значением для k , и он будет генерировать (n 1) - k много запусков. Итак, сделайте это, и вы получите:

 9, 8, 7, 6, 5, 4, 3, 2, 1
      7, 6, 5, 4, 3, 2, 1
            5, 4, 3, 2, 1
                  3, 2, 1
                        1
  

Суммируйте их, и вы, наконец, получите общее количество прогонов:

 9   8   7   6   5   4   3   2   1
        7   6   5   4   3   2   1
                5   4   3   2   1
                        3   2   1
                                1
  

Что дает r = 95 результат.

Формула и доказательство

Точная формула для этого:

 sum_{i = 1}^{n - 1} ceil((n - i) / 2) * i
  

Если вы отбросите ceil (это не повлияет на сложность), вы можете упростить это до

 n^3 / 12 - n / 12
  

И теперь вы можете легко увидеть и доказать, что это так O(n^3) .