相关代码：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，则去除与这个项目相乘的常数，得到的结果就是大O阶。
- 可以根据算法的名称推算时间复杂度。(从算法思想上计算)。
对于一些算法，它们的时间复杂度不是固定的，存在最好和最坏的两种情况：
- 最坏情况：任意输入规模的最大运行次数（上界）。
- 平均情况：任意输入规模的期望运行次数。
- 最好情况：任意输入规模的最小运行次数（下界）。
实例
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。
- 每调用一次其他函数，开辟一个新的栈帧，有额外的空间复杂度。
- 函数的形式参数也算空间复杂度的一部分。
时间复杂度不计算时间，计算的是大概的运算次数。
空间复杂度不计算空间，计算的是大概定义的变量个数。
