Увеличивается ли в цикле экспоненциальное время?

Question

У меня есть простое, но запутанное сомнение в том, что приведенная ниже программа работает в экспоненциальном времени. Вопрос в том, что: введя целое число + ve, распечатайте его. Подвох в том, что вы сознательно делаете это в цикле , например:

int input,output=0;
cin >> input;
while (input--) ++output; // Takes time proportional to the value of input
cout << output;

Я утверждаю, что эта проблема работает в геометрической прогрессии. Потому что, как только вы увеличиваете количество бит на входе на 1, программе требуется вдвое больше времени для выполнения. Другими словами, для распечатки log2 (входных) битов требуется O (входное) время.

Правильно ли это рассуждение?

Answer 1

Вы как бы ответили на свой вопрос:

// Принимает время, пропорциональное значению ввода

Это именно то, что происходит. Если вы удвоите ввод, вы удвоите время. Если вы утроите его, вы втрое увеличите время.

т. стоимость = постоянная * input_size

То, что вы видите, является линейным отношением для input_size.

Экспоненциальные отношения будут выглядеть примерно так:

стоимость = постоянная * (input_size) ^ x

Где это Х, ты меняешься. Здесь дело не в этом.

Answer 2

Вы можете сказать, что это экспоненциально, но в конце концов оно все равно будет O(input).

Размер ввода O(log input). Как вы сказали, удвоение значения удваивает время:

1 bits => 1 increments max
2 bits => 4 increments max
3 bits => 8 increments max
...
n bits => 2^n increments max

Таким образом, время выполнения составляет O(2^log(input)) = O(input). Таким образом, вы могли бы сказать, что это экспоненциальное число бит или линейное значение. Это то же самое. Обычно вы говорите, что оно линейно по значению input.

Answer 3

Я думаю, что вы немного запутались, когда рассуждаете:

в тот момент, когда вы увеличиваете количество бит на входе на 1, программе требуется удвоенное количество времени для выполнения

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