相关代码：SData/test_22/main.c · Hera_Yc/bit_C_学习 - 码云 - 开源中国

数据结构：在内存当中存储、组织数据的方式。（顺序表、链表、栈、队列、树等）。

算法：与数据结构配合使用，是对数据的处理。（查找、排序、二分查找、动态规划等）。

复杂度：用来分析算法的性能，算法的性能分为时间开销和空间占用两个部分。

        现代计算机，对空间复杂度的要求很低了。根据摩尔定律，现代计算机的内存已经是相当大的，对于几个字节的额外开销，这些空间复杂度可以忽略不计了。（1GB大约可以定义2千5百万个int）。

---

时间复杂度

        算法的时间复杂度是一个函数，它描述了该算法的运行时间。从理论上讲，执行一段算法所消耗的时间是不可计算的。因此：

时间复杂度：描述算法中基本操作的执行次数。

大O渐进表示法

void Func(int N)
{int count = 0;int i = 0;int j = 0;for (i=0; i < N; i++){for (j=0; j < N; j++){count++;}}int M = 10;while (M--){count++;}printf("%d\n", count);return;
}
//F(N)=N*N+2*N+10
//用大O的渐进表示法表示
//O(N)=N*N

        实际计算中，我们并不一定要精确的计算，只需要大致的执行次数，因此我们这里使用大O渐进表示法。

推导大O阶方法：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行函数中，只保留最高项。
3. 如果最高项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶。
4. 可以根据算法的名称推算时间复杂度。(从算法思想上计算)。

对于一些算法，它们的时间复杂度不是固定的，存在最好和最坏的两种情况：

• 最坏情况：任意输入规模的最大运行次数（上界）。
• 平均情况：任意输入规模的期望运行次数。
• 最好情况：任意输入规模的最小运行次数（下界）。

实例

1、O(M+N)

int Func2(int N, int M)
{int i = 0;int count = 0;for (i = 0; i < N; i++){count++;}for (i = 0; i < M; i++){count++;}return 0;
}
//O(M+N)

2、 O(1)

void Func3(int N)
{int k = 0;int count = 0;for (k = 0; k < 100; k++){count++;}
}
O(1)

 3、冒泡排序的时间复杂度

//冒泡排序
//时间复杂度O(N^2)
//最好情况是O(N)
#include <assert.h>
void BubbleSort(int a[],int n)
{assert(a);size_t end = 0;for (end = n; end > 0; end--){int exchange = 0;size_t i = 1;for (i = 1; i < end; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange = 0)break;}}

 4、二分查找的时间复杂度

int BinSearch(int* arr,int sz,int oj)
{int left = 0;int right = sz - 1;int mid = 0;while (left < right){mid = left + (right - left) / 2;if (arr[mid] < oj){left = mid + 1;}if (arr[mid] > oj){right = mid - 1;}if (arr[mid] == oj){return arr[mid];}}return -1;
}

 根据二分查找的算法逻辑来推算时间复杂度：

• 最好的情况：一次找到，O(1)
• 最坏的情况：最后一次找到：log2(N)
• 时间复杂度：O(log2(N))

5、递归函数（初步认识、后面补充）

//求阶乘
//O(N)
//递归算法如何计算：递归次数*每次递归函数的次数
long long Fac(size_t N)
{return N < 2 ? N : Fac(N - 1) * N;
}

6、斐波那契（）

---

空间复杂度

空间复杂度：计算的是定义的变量个数，包括调用其他函数的栈帧。

空间复杂度的计算与时间复杂度类似：

1. 用常数1取代运行时间中的所有加法常数。
2. 每定义一个变量，空间复杂度+1。
3. 每调用一次其他函数，开辟一个新的栈帧，有额外的空间复杂度。
4. 函数的形式参数也算空间复杂度的一部分。

时间复杂度不计算时间，计算的是大概的运算次数。

空间复杂度不计算空间，计算的是大概定义的变量个数。