考研数据结构必须掌握的知识点
程序员文章站
2022-07-13 21:10:47
...
1.时间复杂度比较(及空间复杂度)
时间复杂度判断理论:O(1) <= O(log2(n)) <= O(n) <= O(n*log2(n)) <= O(n^2) <=...<=O(n^k) <= O(2^n)
空间复杂度判断理论:
属性 | 大小 |
char( unsigned char / signed char) | 1个字节 |
short int( unsigned short int / signed int) | 2个字节 |
int( unsigned int / signed int) | 4个字节 |
long int( . /. ) | 8个字节 |
float | 4个字节 |
double | 8个字节 |
long double | 16个字节 |
注意:一个字节8位二进制数。
个人成长路程
阶段一:看到一个程序能够很快看到它的算法的时间复杂度(最大时间复杂度)。
阶段二:能够就算出每一部分的(时间复杂度)最大时间复杂度。
阶段三:能够精确的找到可以优化的步骤并找到合适的方式进行优化。
阶段四:找到全部可以优化的步骤,用你自己所学的最好的方式进行优化,充分考虑时间复杂度,和空间复杂度。
遇到的问题:
例子:求出下列算法的时间复杂度。
void fun(int n){
int i = 1, j = 100; //空间为 8个字节
while( j < n ){ //时间为 n次循环
++j;
i+=2;
}
}
分析:
第一步:找出基本操作,确定规模n
a:找基本操作(基本操作就是其重复执行次数和算法的执行时间成正比的操作)重复最多的(最大时间复杂度)
++j;
i+=2;
b:确定规模,基本操作执行的次数。
i < n;循环执行的操作和n有关,因此参数n就是规模n。
第二步:计算出n的函数f(n)
i 初值为 1
i+=2
则时间复杂度为:n/2, 因此时间复杂度为:n。
必须要练习的题目:你所遇到的所有算法题都要进行分析。
上一篇: Spring——@Enable***注解的工作原理
下一篇: 第三章 栈与队列