как определить временную сложность этого вложенного цикла для

Question

Я хочу, чтобы вычислить сложность этого вложенная цикл:

for (int i = 0; i < n; i++) { 
    for (int j = i + 1; j < n; j++) { 
     for (int k = j + 1; k < n; k++) { 
      //do something here 
     } 
    } 
} 

Как рассчитать сложность?

Answer 1

• на самом деле, это три для петель является хорошим способом, чтобы получить количество всех различных комбинаций выбора 3 элементов из п элементов.
• он равен C (n, 3). и C (n, i) -> O (n^i).
• так что ответ O (n^3).

Answer 2

Сколько раз вы достигаете тела внутренней петли?

Это выбирает каждую комбинацию из 3-х элементов из [0, п) (в I, J, K)

Есть п * (п-1) * (п-2)/3! = (n^3 - 3n^2 + 2n)/6 из них.

Сложность это O (N^3)

Answer 3

Это просто: есть три петли, каждая петля представляет собой сложную временную сложность O (n).

Так что это O (n^3).