下面两个程序的时间复杂度?

问题描述 投票:0回答:1

我知道下面代码的时间复杂度是O(n)。

n = 10
for x in range(0,n): 
    print("")

我也知道下面代码的时间复杂度是O(n^2):

n = 10
for x in range(0,n): 
    for y in range(0,n):
        print("")

我无法确定以下两个程序的时间复杂度。

  1. 在这里,我们有两个单独的循环。每个都有 O(n) 的时间复杂度。那么,整个程序的时间复杂度应该是O(n + n)吗?还是别的什么?
# program 1
 
n = 10
for x in range(0,n): 
    print("")

for y in range(0,n): 
    print("")
  1. 在这里,我们又有两个单独的循环,但第一个循环的时间复杂度为 O(n^2),第二个循环的时间复杂度为 O(n^3)。那么,整个程序的时间复杂度应该是O(n^2 + n^3)吗?还是别的什么?
# program 2

n = 10
for x in range(0,n): 
    for y in range(0,n): 
        print("")

for a in range(0,n): 
    for b in range(0,n): 
        for c in range(0,n): 
            print("")
time-complexity language-agnostic big-o conceptual
1个回答
2
投票

是的,你的第二个程序的复杂度将是 O(n^2) + O(n^3)。您可以得出结论,您的程序的复杂性仅为 O(n^3),因为它是具有最大功效的单项式项。

你的第一个程序的复杂度是 O(n) + O(n) = 2.O(n) = O(n)。你推理得很好。复杂度为 O(n)

© www.soinside.com 2019 - 2024. All rights reserved.