初学者关于算法复杂度的学习笔记

1.前言

1.1数据结构（Data structure）

数据结构是计算机储存、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

1.2算法（Algorithm）

算法就是定义良好的计算过程，简单来说就是一系列计算步骤，用来将输入的数据转化为输出的结果。

2.算法的效率

一个算法的好坏通常用复杂度来衡量（复杂度越小，效率越高），包括时间复杂度和空间复杂度

 2.1时间复杂度（衡量一个算法运行的快慢）

由于计算机的配置，编译环境的差异以及运行时间的不可预测性（只能写完代码测试才能知道不好通过理论思想来评估。）我们不直计算时间来衡量计算效率，从而引入时间复杂度。

定义：在计算机科学中，算法的时间复杂度是一个函数式T(N)，这个T(N)函数式计算了程序的执⾏次数，那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)，假设每句指令执⾏时间基本⼀样(实际中有差别，但是微乎其微)，那么执⾏次数和运⾏时间就是等⽐正相关，这样也脱离了具体的编译运⾏环境。

我们计算时间复杂度的目的实际上是比较算法程序的增长量级，所以计算出精确的执行次数意义也不大，也就是说时间复杂度衡量的是随变量N的变化，算法运行时间的变化，而不是聚焦于计算一个具体的值。

所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。

2.2大O的渐进表示法

推导大O阶规则：

1.只保留最高阶

2.最高阶存在且不是1，去除常系数

3.只有常数一律用1取代所有加法常数

3.时间复杂度的计算示

3.1示例1

// 计算Func2的时间复杂度？
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N ; ++ k)//-------2n{++count;}int M = 10;while (M--)//---------------------------10{++count;}printf("%d\n", count);
}

T(N)=2N+10

O(N)

不是计算语句的执行次数吗，为什么不用算其他的语句如：int count = 0;、printf("%d\n", count); 

• 像这样的语句，其执行时间不随输入规模变化，是 O(1) 的操作。

• 在大多数情况下，这些操作的时间复杂度可以忽略，因为它们不会影响整体的增长趋势。

 3.2示例2

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++ k)//-----------------M{++count;}for (int k = 0; k < N ; ++k)//-----------------N{++count;}printf("%d\n", count);
}

T(N)=M+N

O(M+N)     这里我们不确定M和N大小

这里可以进一步讨论：

• M>>N     O(M)
• N>>M     O(N)
• N==M     O(N)或者O(M)

3.3示例3

// 计算Func4的时间复杂度？
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++ k)//------------100{++count;}printf("%d\n", count);
}

O(1)

3.4示例4

// 计算strchr的时间复杂度？
const char * strchr ( const char* str, int character)
{const char* p_begin = s;while (*p_begin != character){if (*p_begin == '\0')return NULL;p_begin++;}return p_begin;
}

有些算法的时间复杂度存在最好、平均和最坏情况。

最坏情况：任意输⼊规模的最⼤运⾏次数(上界)

平均情况：任意输⼊规模的期望运⾏次数

最好情况：任意输⼊规模的最⼩运⾏次数(下界)

⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。

按照最差的情况来看，最多要找N次

O(N)

3.5示例5

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}if (exchange == 0)break;}
}

最差的情况：数据排列为降序

O(N^2) 

3.6示例6

void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

 O(logn)

3.7示例7

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}

函数递归，时间复杂度 =递归次数递归次数*单次递归的时间复杂度 

4.空间复杂度

4.1空间复杂度的计算

4.1.1示例1

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

4.1.2示例2

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}