Что будет временная сложность для вложенных цикловКак я могу проанализировать временную сложность этого алгоритма?
for (i=1; i<=n; i++) {
for (j=1; j<=log(i); j++) {
O(1);
}
}
где n задается пользователем? Связана ли временная сложность только с переменными цикла или с условным <=?
Сложность времени обычно не зависит от пользовательского ввода (в данном случае: n). Первый цикл будет выполнять n итераций, а второй цикл будет выполнять логические (n) итерации в худшем случае. Поскольку вы не предоставили тело цикла, считая операции в цикле O (1), тогда сложность O (n log n).
Что касается вашего второго вопроса, это зависит как от вашей петли, так и от «сравнения части» (тела контура).
Временная сложность зависит от всего, что требует времени, поэтому да, это зависит от границ цикла for. Обычно лучше всего анализировать петли изнутри. Таким образом,
for (j=1; j<=log(i); j++) {
O(1);
}
займет O(1)*log(i)=O(log(i)) раз. Затем мы можем написать весь цикл как
for (i=1; i<=n; i++) {
O(log(i));
}
Самое простое в этом вопросе - просто добавить все это. Общее время поэтому:
O(log(1))+O(log(2))+O(log(3))+...+O(log(n-2))+O(log(n-1))+O(log(n))
=O(log(1) + log(2) + log(3) +...+ log(n-2) + log(n-1) + log(n))
Из-за свойств логарифмов, это O(log(n!)), и Stirling’s approximation, это O(n log(n)).
Что означает «зависит ли временная сложность от переменной инкремента цикла или сравнения всей части»? Именно там, где вы пытаетесь вычислить сложность времени? –
Добро пожаловать в переполнение стека. Я отредактировал ваше сообщение, чтобы исправить грамматику, и сделал ваш алгоритм законченным, поместив некоторый код «O (1)» во внутренний цикл. Я также удалил приветствия в начале и в конце вашего сообщения - вот как мы делаем вещи в Stack Overflow. Я должен был сделать некоторые предположения о том, что вы на самом деле имели в виду под «переменной приращения цикла» и «сравнением части»; если я ошибочно принял, пожалуйста, отредактируйте это. – Teepeemm