упражнение в моей книге просит меня, чтобы вычислить время выполнения следующих действий для цикла:Каково время работы следующей программы?
for (int i = 0; i < n; ++i)
++k;
Это сразу напоминает мне суммирования нотации. Поэтому я записываю соответствующий синтаксис:
Правильно ли это? Если нет, то почему нет - и как я могу рассчитать его правильно?
Давайте посмотрим на операции внутри цикла:
++k;
Независимо от того, что k в том, что операция не займет постоянное время. Поэтому заменим его на O(1).
for (int i=0; i<n; ++i)
O(1)
Мы можем видеть, что мы будем перебрать O(1) блока n раз. Так что:
O(n) * O(1)
Что, очевидно, равна:
O(n)
В следующей книге мы не используем синтаксис 'O'. Мы разрушаем уравнения, представляющие код. Так что в этом случае это похоже на суммирующую нотацию в моем вопросе. –
Возможно, ваша книга ищет '\ sum_ {i = 1}^{n} 1'? Но я могу только помочь с обозначением, которое знаю. Если вы хотите прочитать эту нотацию, [здесь ссылка на wikipedia] (https://en.wikipedia.org/wiki/Big_O_notation). –
Ваш код суммирует '1 + 1 + 1 + ...' 'n' раз. Мой код добавляет 'k + 1 + 1 ...' - 'k' не может начинаться с' 1'. –
Это правильно?
Нет. Это не так.
Если нет, то почему нет - и как я могу рассчитать его правильно?
k увеличивается на 1 в каждой итерации, т.е. n добавляется к нему, когда цикл завершается. Таким образом, k = k + 1 не равен k = k + k.
Время выполнения кода порядка n, потому что цикл работает n раз и ++k выполняется в постоянное время внутри цикла.
Все, что вы здесь делаете рассчитывает. Если я понимаю ваше упражнение, это связано с измерением времени часов. Для этого вам нужно будет использовать высокоточную функцию часов. – Logicrat