数据结构与算法-入门

数据结构，一种或多种特定关系数据元素集合

  • 逻辑结构
    • 集合结构：元素间没有联系，但存在于同一个集合中
    • 线性结构：元素间存在一对一的关系
    • 树形结构：元素间存在一对多的关系
    • 图形结构：元素间存在多对多的关系
  • 物理结构
    • 顺序存储结构：元素的存储地址是连续的
    • 链式存储结构：元素存储的地址不连续，通过引用指针来找到关联的元素

算法，计算机用来解决问题的方法

时间复杂度

对算法消耗时间的分析，称为时间复杂度分析

时间频度T(n)

  • 一个算法所消耗的时间和代码执行次数成正比
  • 执行次数越多消耗的时间越多
  • 一个算法的语句执行的次数被称为时间频度T(n)

例如：计算1-10000的和

  • 方式一
1
2
3
4
int sum=0;
for(int i=1;i<=10000;i++){
    sum+=i;
}

使用for循环计算，计算时间频度是T(n) = n+1，最后一次循环也要判断所以+1，常数项可以省略，所以T(n) = n；

  • 方式二
1
int sum=(1+10000)*10000/2;

使用公式计算，时间频度是T(n) = 1;

算法函数中的，常数项、低次项、系数都可以省略

T(n) = n + 10 -> T(n) = n

T(n) = n^2 + 2n +10 -> T(n) = n^2

大O计数法

在算法中，时间复杂度的分析，使用大O计数法

  • T(n) = O(f(n))，T(n)受限于f(n)

  • 当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”

  • 常数阶 O(1)

1
2
3
4
5
public static void main(String[] args) {
    int a= 0;
    ++a;
    int c =a+1;
}

这个代码不管是执行了多少行，只要没有循环等这种复杂的结构，那时间复杂度就是O(1)

  • 线性阶O(n)
1
2
3
4
int sum=0;
for(int i=1;i<=10000;i++){
    sum+=i;
}

for循环里面的代码会执行n次，因为随着n的变化所消耗的时间也随之线性变化，这类的代码都可以使用O(n)来表示

  • 平方阶 O(n²)
1
2
3
4
5
6
7
int sum= 0;
int n=10;
for(int j = 1;j<=n;j++){
    for(int i =1;i<n;i++){
        sum+=i;
    }
}

这段代码n是10，外层会循环执行10次，内层会循环执行10次，总共执行10*10=100次，也就是n的平方次，使用O(n^2)来表示。同理，如果使用了三层循环那么时间复杂度就是O(n^3)立方阶

  • 对数阶O(Logn)
1
2
3
4
5
int i=1
int sum=100
while(i<sum){
    i=i*2
}

这里的while循环，每经过一轮，也就是每经过一次i*2的运算，结果就会和sum的值更近 2^x=n，时间复杂度就是O(Logn)

时间复杂度由小到大排序

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(n^k)<O(2^n)

可以看出随着规模n的不断变大，执行的效率就越低

平均时间复杂度与最坏时间复杂度

  • 平均时间复杂度说的是任何的算法时间复杂度都是O(n²)
  • 最坏情况时间复杂度每次都是查到到最后一个才是期望数字O(n²)

空间复杂度

一个算法的空间复杂度定义是该算法所消耗的存储空间