сложность Время вложенной для различных структур цикла

Question

У меня есть кусок кода, который выполняет три вложенные для петель следующим образом (написано как язык агностика, как это возможно):

for i = 0 to n - 1 
    for j = 0 to n - 1 
     for k = 0 to n - 1 
      [do computation in linear time] 

Моей интуиция говорит, что это должно привести к в сложности N^3. Я хотел бы сравнить его сложность следующих вложенных циклов:

for i = 0 to n - 1 
    for j = i + 1 to n - 1 
     for k = j + 1 to n - 1 
      [do computation in linear time] 

Логически, это должно быть быстрее, потому что, как i увеличивается, внутренние циклы должны вычислить быстрее; однако, увидев на сайте множество других потоков, объясняющих, что последний из них также N^3 запутан.

Является ли мое предположение о N^3 для обоих правильных, и если да, то как я могу количественно определить различия, если они есть?

Answer 1

С большой нотой обозначается только первое значение полинома (т. Е. В этом случае N^3). Последний пример, который вы предоставляете, может быть описан как (N^3) -b (N^2) -c (N) -d, где {a, b, c, d} - целые числа, и, следовательно, последнее может быть значительно быстрее, в зависимости от того, насколько большой или малый i или n. Однако, поскольку у вас есть 3 вложенных цикла, запись с большим О будет по-прежнему отображаться как N^3.

Answer 2

Сложность времени для обоих приведенных выше кодов будет порядком n^3 i, e Big O (n^3). По определению записи Big O T (n) ≤ k f (n) для некоторой константы k. Таким образом, второй код не будет в большей степени способствовать некоторой константе k.