Сложность времени: простой расчет l oop

Question

У меня есть простой l oop, подобный этому:

for (int i = 0; i < n; i++) {
  // constant time operation
}

Очень легко увидеть, что он имеет O (n) сложность по времени, но если мы его вычислим, почему это 2*n + 2 + c*n (дан ответ) а не (1+ (n+1) + 2*n + c*n) = (3+c)*n + 2? Я вижу i++ как 2 операции: добавление и присваивание; таким образом, оно должно быть 2*n, а постоянная операция выполняется n раз, поэтому c*n.

Answer 1

Из того, что я могу сказать, увеличение / уменьшение рассматривается как одна операция. Это имеет смысл, потому что в сборке вы можете выполнять увеличение или уменьшение с помощью одной строки кода сборки. Кроме того, большинство строк ассемблерного кода переводятся непосредственно в одну двоичную инструкцию. Таким образом, увеличение / уменьшение по сути является операцией с постоянным временем.

Следовательно, у нас есть n операций от приращения. Мы также запускаем тело l oop n раз, а тело l oop выполняет операцию с постоянным временем, поэтому у нас есть дополнительные c * n операции. Когда мы вводим l oop в первый раз, происходит дополнительная операция присваивания. Это приводит к другой операции. Наконец, после того, как l oop запустится в n-й раз, l oop проверяет состояние l oop еще раз. Это означает, что есть n + 1 сравнений, которые выполняет l oop.

Сложив их, мы имеем n + c * n + 1 + (n + 1) = 2 * n + c * n + 2, ответ, который вы видели.

Answer 2

2*n

(n сравнения (i<n) + n приращения (i++)) == 2*n

2

(i=0 1 для назначения + 1 для выделения i) == 2

c*n

(n операции с постоянным временем) == c*n