根据a和b，以下算法的运行时复杂性是多少

Question

我想知道这个函数在两个变量方面的时间复杂性是多少。我的猜测是O(a*b(，因为while循环使用a和b。

def somefunc(a, b):
def anotherfunc(current, num_digits):
if num_digits == 0:
print(current)
else:
print_01_codes('0' + current, num_digits - 1)
print_01_codes('1' + current, num_digits - 1)
upper_bound = 0
while True:
for i in range(upper_bound):
print_01_codes('', a)
if upper_bound > b:
break
upper_bound += 1

Answer 1

由于a从未用于确定循环的迭代次数，因此复杂性应为O(b^2)，因为内部循环将迭代b^2/2次。

Answer 2

您的外部while True:循环实际上是for upper_bound in range(b+1):写得更模糊，所以它显然运行了b+1次。

您的内循环是for i in range(upper_bound):，而upper_bound的平均值是(b+1)/2，所以它每个外循环运行(b+1)/2次，或者总共运行(b+1) * (b+1)/2次。

您没有向我们展示print_01_codes('', a)的定义，也没有告诉我们a和b的值是什么。

• 如果a是某种集合，并且print_01_codes在a中的值上循环(就像print('', a)一样(，则该循环在每个内部循环中运行a次，或者总共运行(b+1) * (b+1)/2 * a次
• 如果a只是一个数字，并且它只是打印出来的(就像print('', a)一样(，则需要log(a, 10)时间

同时，anotherfunc中的所有代码都是无关的，因为该函数永远不会被调用。

所以，你的时间不是O(a * b)，而是O(a * b**2)或O(log a * b**2)。