时间:2021-10-05
类型:日常干货笔记
记录人:swu_LCY
- 衡量时间效率和空间效率,最主要关注时间效率. 算法中的基本操作的执行次数,为算法的时间复杂度,而不是具体时间.
- 算法中空间复杂度是在计算变量的个数,是一个算法在运行过程中临时占用储存空间大小的量度,而不是在计算程序占用了多少bytes的空间
时间复杂度是一个估算,是去看表达式中影响最大的那一项.
规则一
- 1.用常数1取代运行时间中的所有加法常数
- 2.在修改后的运行次数函数中,只保留最高阶项
- 3.如果最高阶项存在且不是1,则去除这个项目相乘的常数,得到的结果就是大O阶
规则二
算法的时间复杂度存在最好、平均和最坏的情况:
(悲观预期,看最坏的打算)
- 1.最坏情况:任意输入规模的最大运行次数(上界)——O(N)
- 2.平均情况:任意输入规模的期望运行次数——O(N/2)
- 3.最好的情况:任意输入规模的最小运行次数(下界)——O(1)
- 1.冒泡排序
- 2.折半查找
- 3.阶乘递归(斐波那契为例)
eg.
long long Factorial(size_t N)
{
return N<2 ? N:Factorial(N-1)*N;
} - 动态内存管理
- malloc()
- 递归
- 循环
- 不是一层循环就是O(N),两层循环就是O(N^2),要看具体程序.
- “算法”的复杂度计算,喜欢省略成logN,因为很多地方不好写底数.
- 有些书本,或者网上的资料会写成0(lgN),严格来说这个是不对的
- 时间是累计的,空间不是累计的——循环走了N次,重复利用的是一个空间
- 递归调用了N层,每次调用建立一个栈帧,每个栈帧使用了常数个空间——O(1)
- O(N)
- O(N^2)
- O(logN)——(很牛)
- O(1)——(最牛)
