Определения большого-O данного алгоритма

Question

Я дал этот алгоритм (псевдо-код, а не в каком-либо конкретном языке):

foo1(l,m,n){ 
    for (i = 1; i < l, i++){ 
     for(j = 1; j < m ; j++){ 
      for (k = 1; k < n; k++){ 
      //Constant time inner loop 
      } 
     } 
    } 
} 

Я пытаюсь найти количество раз он внутреннего цикл бежит в относительно l, m, и n и придумать для этого функцию. Я также пытаюсь вычислить нотацию Big-O для алгоритма.

Глядя на алгоритм, я думал, что внутренний цикл будет работать l * m * n раз. Я придумал это, потому что, например, если l, m, n были 3, 6, 9 соответственно, тогда внутренний цикл будет работать (9 * 6 * 3) раз. Таким образом, функция, которая будет возвращать количество раз пробегов внутреннего цикла будет что-то вроде:

f = l*m*n 

Теперь большой-O, где я борюсь с (не обязательно с этой проблемой), но я хотел бы получить некоторые более глубокое понимание того, как решать проблемы большого О, чтобы лучше определить правильный большой-O для алгоритма.

Для этого конкретного случая я думал, что big-O будет n^3, но это просто основано на предположении действительно. Как мне разобраться, что такое big-O для этой проблемы, и в целом для других алгоритмов, с которыми я могу столкнуться?

Answer 1

Вы находитесь на правильном пути понимания big-O. Над псевдокод действительно имеет сложность O (л м п) Как вы, вероятно, ищете некоторые ссылки, я бы хотел, чтобы вы посмотрите на следующий удивительный посте на самом переполнение стека:

Plain English explanation of Big-O

На мой взгляд, это одно из лучших руководств, чтобы вы начали с концепций Big-O.

Если вы углубитесь в глубину, следуйте this MIT Lecture. Это, безусловно, даст вам приятную езду о концепциях Big-O в деталях. Я думаю, что эти две ссылки помогут вам разобраться в ваших концепциях и определенно помогут вам в создании вашего твердого понимания.

Happy Leaning!