У меня есть простой цикл, как это:
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.
2*n
(n сравнений (i<n) + n приращений (i++)) == 2*n
2
(i=0 1 для назначения + 1 для выделения i) == 2
c*n
(n операции с постоянным временем) == c*n
Насколько я могу судить, увеличение/уменьшение рассматривается как одна операция. Это имеет смысл, потому что в ассемблере вы можете выполнять увеличение или уменьшение с помощью одной строки ассемблерного кода. Кроме того, большинство строк ассемблерного кода преобразуются непосредственно в одну двоичную инструкцию. Таким образом, увеличение/уменьшение фактически является операцией с постоянным временем.
Следовательно, у нас есть n операций приращения. Мы также запускаем тело цикла n раз, и тело цикла выполняет операцию с постоянным временем, поэтому у нас есть дополнительные c * n операций. Когда мы входим в цикл в первый раз, происходит дополнительная операция присваивания. Получается еще одна операция. Наконец, после того, как цикл запустится в n-й раз, цикл еще раз проверяет условие цикла. Это означает, что цикл выполняет n + 1 сравнений.
Суммируя их, мы имеем n + c * n + 1 + (n + 1) = 2 * n + c * n + 2, что и является ответом, который вы видели.
