就 n 和 m 而言，运行 时间复杂度是多少？
What is the run-time complexity in terms of n and m?
这是一道编程面试题。
根据 n 和 m，以下算法的 运行 时间复杂度是多少？
def print_all_codes(n, m):
def print_01_codes(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('', n)
if upper_bound > m:
break
upper_bound += 1
while True:
for i in range(upper_bound):
print_01_codes('', n)
if upper_bound > m:
break
upper_bound += 1
这个循环与这个相同：
for i in range(m):
for j in range(i):
#Function
这个循环时间复杂度是这样的：
1 + 2 + 3 + 4 + ... + m-1 => (m-1)*(m) / 2 => O(m^2)
关于你的#Function：
if num_digits == 0:
print(current)
else:
print_01_codes('0' + current, num_digits - 1)
print_01_codes('1' + current, num_digits - 1)
这是一个递归函数，就像一个完整的二叉树。所以它是 O(2^n)。
您的代码时间复杂度为 O(m^2 * 2^n).
这是一道编程面试题。 根据 n 和 m，以下算法的 运行 时间复杂度是多少？
def print_all_codes(n, m):
def print_01_codes(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('', n)
if upper_bound > m:
break
upper_bound += 1
while True:
for i in range(upper_bound):
print_01_codes('', n)
if upper_bound > m:
break
upper_bound += 1
这个循环与这个相同：
for i in range(m):
for j in range(i):
#Function
这个循环时间复杂度是这样的：
1 + 2 + 3 + 4 + ... + m-1 => (m-1)*(m) / 2 => O(m^2)
关于你的#Function：
if num_digits == 0:
print(current)
else:
print_01_codes('0' + current, num_digits - 1)
print_01_codes('1' + current, num_digits - 1)
这是一个递归函数，就像一个完整的二叉树。所以它是 O(2^n)。
您的代码时间复杂度为 O(m^2 * 2^n).