Анализ сложности / времени выполнения псевдокода с использованием нотации big-O

Question

Мне нужно немного помочь с проблемой. Я только начал читать о O-нотации, но я все еще новичок, когда дело доходит до анализа кода.

Так вот в чем проблема:

Дается следующий псевдокод, где A - числовое поле, элементы которого могут быть доступны через индексы от 1 до длины (A)

1: procedure Adder(A)
2:      for i <- 1 to length(A)
3:          for j <- length(A) to 1 do 
4:              if i ≠ j then
5:                 A[i] <- A[i] + A[j]

Приведите сложность следующих строк кода в формате big-O:

1. строки 4-5
2. строки 3-5
3. строки 2-5

Так что для строк 4-5 я подумал, что это должен быть просто O (1), поскольку он просто добавляет 2 элемента.

С двумя другими я действительно не уверен.

Для строки 3-5 я думаю, что это должно быть O (n), где n - количество индексов в числовом поле.

И, наконец, для строк 2-5 я бы сказал, что это O (n ^ 2), так как теперь нам нужно циклы?

Answer 1

Мне кажется, это правильно, хотя вы можете переформулировать некоторые обоснования, которые у вас есть

строки 4-5 Я думал, что это должно быть просто O (1), так как это просто добавляет 2 элемента.

Это O (1), потому что независимо от того, какой ввод , алгоритм в конечном итоге будет выполнять 1 или 2 инструкции. Это никогда не будет расти больше чем 1 или 2

наконец, для строк 2-5 я бы сказал, что это O (n ^ 2), так как теперь мы должны петли

Это O (n ^ 2), потому что вложенные циклы повторяются в последовательности, которую вы вводите. Независимо от того, что произойдет, если вход имеет длину N, вам придется сделать N циклов, а N циклов внутри. Таким образом, вы в конечном итоге с N * N, который является N ^ 2, как вы предложили.