algo(n)
for i in 0 to n {
for 0 to 8^i {
}
}
for i to 8^d {
}
Любой вид анализа или информации о временной сложности этого алгоритма будет полезен. Худший случай, лучший случай, нижняя/верхняя граница, theta/omega/big-o, рекуррентное отношение .... и т. Д.Сложность времени для этой функции?
Ваш алгоритм работает в экспоненциальном времени (T ∈ Θ(c^n), c>1). Вы можете проанализировать количество итераций внутреннего for цикла (... for 0 to 8^i) с помощью Sigma обозначения:
Поскольку ваш алгоритм в Θ(8^n), он также находится в O(8^n) (верхний асимптотической оценке) и Ω(8^n) (нижний асимптотическим связанно).
Приведенные выше анализ выполняется в предположении, что d в конечном счете for петли меньше или равен n, и в этом случае вложенных два for цикла до она будет доминировать (и, следовательно, мы needn» t проанализировать последний недоминирующий цикл for).
алго (п) в основном состоит из двух частей:
for i in 0 to n
for 0 to 8^i
и
for i to 8^d
Давайте начнем с первого. Предполагая, что каждая итерация внутреннего цикла занимает постоянное время, сложность C*8^i. Теперь, если суммировать его по возможным значениям i мы получаем:
8^0 + 8^1 + 8^2 + .... + 8^n-1
Это sum of geometric series с a=1, r=8, и его сумма равна:
1 * (1-8 ^(n-1))/(1-8) = 1 * (-1/7 + 8^(n-1)/7)
Для n->infinity, это может быть аппроксимирована 8^(n-1)/7, и мы можем завершить сложность Θ(8^(n-1)/7) = Θ(8^n)
Что касается 2-й части, это довольно прямолинейно и составляет 8^d.
Это дает общее сложность T(n) в Θ(8^d + 8^n)
Каковы ваши собственные мысли? Я был бы рад помочь, но я думаю, что вы узнаете больше, если сначала станете честной попыткой своей собственной. Кроме того, добавьте фигурные скобки ('{', '}') к указанному выше, чтобы мы могли видеть область цикла 'for'. Как есть, кажется, что третий цикл 'for' ** не вложен в два предыдущих, это как предназначено? – dfri
Что такое 'd' в' для i до 8^d'? – amit
Я не знаю, как правильно это записать, но моя попытка временной сложности: (сумма (8^i) для i = 0 до n) + 8^d. Теперь я добавлю фигурные скобки. –