数据结构前言
什么是数据结构？
数据结构是计算机存储，组织数据的方式，相互之间存在一种或多种特定关系的数据元素的集合。
数据结构与数据库的区别
数据结构：在内存中管理数据--增删查改 数据库：在磁盘中管理数据--增删查改
什么是算法？
算法：一系列的计算步骤，将输入数据转化成输出结果。
算法效率
如何衡量一个算法的好坏
从时间复杂度和空间复杂度两方面去衡量
算法的复杂度
算法在编写成可执行程序之后，运行需要耗费时间资源和空间资源 便需要从时间复杂度和空间复杂度去衡量算法的好坏
时间复杂度主要衡量一个算法运行的快慢；空间复杂度主要衡量一个算法运行所需要的额外空间。
时间复杂度
时间复杂度的概念
算法的时间复杂度是一个函数，数学中带未知数的函数表达式。算法中基本操作的执行次数，就是算法的时间复杂度。
简单来说便是：找到某条基本语句与问题规模N之间的数学表达式，就是该算法的时间复杂度。
不能纯粹直接数循环，需要观察算法逻辑，计算时间复杂度。
实例如下
计算函数test中a++语句一共执行多少次
void test(int m) { int i = 0; int j = 0; int k = 0; int a = 0; for (i = 0; i < m; i++) { for (j = 0; j < m; i++) { a++; } } for (k = 0; k < 2 * m; k++) { a++; } }
test执行的基本操作次数 F(m) = m*m + 2*m
实际计算时间复杂度时，只需要计算大概执行的次数，这里便需要使用接下来学习的大O的渐进表示法
大O的渐进表示法
大O：用于描述函数渐进行为的数学符号
推导大O渐进法：
用常熟1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶项存在且不为1，则去除最高阶项的常数表达式，得到的结果便是大O。
大O的渐进表达法删去对结果影响不大的项，简介明了地展示出执行次数。
有些算法的时间复杂度存在最好，平均和最坏的情况
最好：任意输入规模的最小运行次数（下界）
平均：任意输入规模的期望运行次数
最坏：任意输入规模的最大运行次数（上界）
实际中关注的是算法的最坏运行情况，所以数组中搜索数据的时间复杂度为O(N)
常见时间复杂度计算
实例1
void test(int m, int n) { int a = 0; int i = 0; for (i = 0; i < m; i++) { a++; } for (i = 0; i < n; i++) { a++; } }
1. m远大于n O(M)
2. n远大于m O(N)
3. m和n一样大 O(N)或者O(M)
实例2
计算冒泡排序的时间复杂度
void Bubblesort(int* str, int n) { assert(str); int i = 0; int j = 0; for (i = n; i > 0; i--) { int exchange = 0; for (j = 1; j < i; j++) { if (str[j] > str[j + 1]) { Swap(&str[j], &str[j + 1]); exchange = 1; } } if (exchange == 0) { break; } } }
实例3
void test(int n) { int a = 0; int i = 0; for (i = 0; i < 10000; i++) { a++; } }
时间复杂度为O(1)，但不代表1次，而是代表常数次。
实例4
计算二分查找的时间复杂度
void Binarysearch(int* str, int n, int k) { assert(str); int begin = 0; int end = n - 1; while (begin <= end) { int mid = begin + (end - begin) / 2; if (str[mid] < k) { begin = mid + 1; } else if (str[mid] > k) { end = mid - 1; } else return mid; } return; }
实例5
计算斐波那契递归时间复杂度
long long Fib(int n) { if (n < 3) { return 1; } return Fib(n - 1) + Fib(n - 2); }
空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中额外占用存储空间大小的量度
空间复杂度计算规则基本与实践复杂度类似，同样使用大O渐进表示法
函数运行所需要的栈空间（存储参数，局部变量，一些寄存器信息等）在编译期间就已经确定好啦，因此空间复杂度主要通过函数在运行时申请的额外空间来确定
空间可以重复利用，不积累；时间一去不复返，需要积累
实例1
计算冒泡排序的空间复杂度
void Bubblesort(int* str, int n) { assert(str); int i = 0; int j = 0; for (i = n; i > 0; i--) { int exchange = 0; for (j = 1; j < i; j++) { if (str[j] > str[j + 1]) { Swap(&str[j], &str[j + 1]); exchange = 1; } } if (exchange == 0) { break; } } }
冒泡排序额外占用的空间只有i,j,exchange，所以空间复杂度为O(1)
实例2
计算斐波那契递归空间复杂度
long long Fib(int n) { if (n < 3) { return 1; } return Fib(n - 1) + Fib(n - 2); }
由于空间可以重复利用，不积累；时间一去不复返，需要积累。所以开辟了N个栈帧， 空间复杂度为O(N)
