O(nⁿ) 使用循环或递归的复杂伪代码结构

Question

O(n) 时间只是一个循环，O(n²) 是一个循环内的循环，其中两个循环运行在 kn 次（k 是一个整数）。这种模式还在继续。但是，O(nᵏ) 的所有有限整数 k 都可以手动构造，您可以简单地将循环嵌套在另一个循环中，但是 O(nⁿ) 呢，其中 n 是接近无穷大的任意值？

我在想 while 循环在这里可以工作，但我们如何设置中断条件。此外，我相信 O(nⁿ) 的复杂性可以使用递归来实现，但从伪代码的角度来看，它看起来如何？

如何仅使用循环或递归构建运行复杂度为 O(nⁿ) 的算法？

Answer 1

一个非常简单的迭代解决方案是计算 nⁿ 然后数到它：

total = 1
for i in range(n):
    total *= n

for i in range(total):
    # Do something that does O(1) work

这可以很容易地递归重写：

def calc_nn(n, k):
    if k == 0:
        return 1
    return n * calc_nn(n, k - 1)

def count_to(k):
    if k != 0:
        count_to(k - 1)

def recursive_version(n):
    count_to(calc_nn(n, n))

O(nⁿ) 使用循环或递归的复杂伪代码结构

O(nⁿ) complexity pseuodocode structure using loops or recursion

algorithm

big-o

time-complexity