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

Time complexity of the following two programs?

提问人:Yash 提问时间:2/22/2023 最后编辑:CrazyChuckyYash 更新时间:2/25/2023 访问量:69

问:

我知道以下代码的时间复杂度为 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("")
与时间复杂 度语言无关的 big-o 概念

评论


答:

2赞 Wend Yam D. Davy Ouedraogo 2/23/2023 #1

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

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

评论

0赞 Yash 2/24/2023
谢谢你的回答。我理解了第二个程序的解释。但是,对于第一个程序,我们怎么能说 2.O(n) 等于 O(n)?
0赞 Wend Yam D. Davy Ouedraogo 2/25/2023
谢谢。O表示渐近表示法,比较渐近表示法有规则。给定一个常数,使得 ,否则 如果 c~=n 则 .cc << nc*O(n) ~= O(n)c*O(n)=n*O(n)