这个功能的时间复杂度？
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 ）。 您可以使用Sigma符号分析内部for循环（ ... for 0 to 8^i ）的迭代次数：
由于你的算法在Θ(8^n) ，它也在O(8^n) （上渐近界）和Ω(8^n) （下渐近界）中。
上述分析是在假设最终for循环分析中的d小于或等于n情况下进行的，在这种情况下，在它之前嵌套的两个for循环将占优势（因此我们不需要分析最后一个非优势for循环明确）。
算法（n）基本上由两部分组成：
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
这是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)
至于第二部分，它非常简单，并且是8 ^ d。
这给出T(n)总复杂度在Θ(8^d + 8^n)