Мне интересно, должна ли большая сложность следующего кода быть o (1) или o (n).Анализ сложности цикла с ограниченным временем цикла
for(int i=0;i<n && n<100;i++){sum++;}
Вот что я думаю: поскольку п ограничена ниже, чем 100, в худшем случае будет O (99) + O (98) + ... + O (1) = 99 * O (1) = O (1) Однако по интуиции код является каким-то образом O (n) из-за цикла.
Был бы очень признателен, если кто-то может посоветовать мне об этом. Спасибо!
Интуитивно это O (1), поскольку при увеличении n время выполнения не увеличивается после определенной точки. Тем не менее, это краевой случай, так как n ограничено гораздо большим числом, скажем, максимальным значением int, оно, казалось бы, не отличается от того, что n не было ограничено вообще. Однако при рассмотрении времени выполнения с использованием теории сложности мы обычно игнорируем такие вещи, как максимальный размер int.
Другим способом думать, что число итераций растет линейно с n для n в (0,100) и является постоянным в противном случае. Однако, учитывая, что n может быть любым значением, алгоритм определенно равен O (1)
Это все предполагается, что каждая итерация цикла занимает постоянное время.
Для получения дополнительной информации см. Теорему Лиувилля.
Спасибо за ваш ответ! –
* алгоритм O (n) для n в (0,100) *, что не имеет смысла. Обозначение Big O определено и применяется только асимптотически при n-> бесконечности. Он не определен ни в одном другом интервале. –
@ A.S.H Я сказал, что это был еще один способ подумать об этом, а затем пояснил, что, поскольку n может быть любой ценностью, алгоритм на самом деле O (1). Я пытался проиллюстрировать, почему алгоритм O (1), и признать, что я, возможно, сделал это плохо. У вас есть предложения по тому, как я могу отредактировать его, чтобы быть более четким? –
Анализ сложности для алгоритмов. Это не имеет смысла только для цикла без дополнительной информации. Что такое цикл? – Anko
Цикл завершает работу с o (1) сложностью. Например. Sum ++; –