欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

考研数据结构必须掌握的知识点

程序员文章站 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。

必须要练习的题目:你所遇到的所有算法题都要进行分析。

 

 

 

相关标签: 考研数据结构