时间复杂度的概念

例1：假设n = 3000 n=3000n=3000

i=2998,print("I love You %d\n",i)
i=2999,print("I love You %d\n",i)
i=3000,print("I love You %d\n",i)

当i=3001,经过判断，i<=n不成立

所以，while循环执行3001次(步骤2)，while循环里面的++、print执行了3000次，其它1、5执行了1次

T(3000)=1+3001+2x3000+1，所以T(n)=3n+3,n=3000

🔥结论：计算时间复杂度只需要考虑阶数高的部分

• 加法规则

多项相加，只保留最高阶的项，并且系数变为1

• 乘法规则

时间复杂度：常[1]、对[logn]、幂[n^2]、 指[2^n]、阶[n!]

🌈时间复杂度的大小关系：

例题

❗易错提醒

1.程序不一定满足有穷性，如死循环、操作系统等；而算法必须有穷

2.算法满足5个基本特性（这是算法的要求而不是定义）

3.算法的时间复杂度为O ( n ² ) ，在这里问题规模是n，时间复杂度是 O ( n ² )

4.在相同的规模下，O ( n ) < O ( n ² )

✅正确！时间复杂度制定了n无穷大，故不能带入特殊值n0考虑

空间复杂度

🍔算法原地工作：算法所需的内存空间为常量

1个int变量占4Byte,32bit

例题

所以，空间复杂度等于递归调用的深度