如何衡量一个算法的好坏呢？比如对于以下斐波那契数列

斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？

long long Fib(int N) 
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

1.2.算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2.时间复杂度

2.1.时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

// 请计算一下Func1中++count语句总共执行了多少次？

void Func1(int N) 
{
int count = 0;
for (int i = 0; i < N ; ++ i) 
{
     for (int j = 0; j < N ; ++ j)
     {
         ++count;
     }
}
 
for (int k = 0; k < 2 * N ; ++ k) 
{
 ++count; 
}
int M = 10;
while (M--) 
{
 ++count; 
}
printf("%d\n", count);
}

Func1 执行的基本操作次数：

N = 10 F(N) = 130

N = 100 F(N) = 10210

N = 1000 F(N) = 1002010

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法

2.2.大O的渐进表示法

上面代码中复杂度如下描述

N = 10 F(N) = 130

N = 100 F(N) = 10210

N = 1000 F(N) = 1002010

我们发现，随着N的变大，后两项对整个结果的影响变小，当N无限大的时候，后两项对结果的影响可以忽略不计

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。（所以有些题限制O(1)不是只能循环一次，而? ? ? ?是可以运行常数次）

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

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

最坏情况：任意输入规模的最大运行次数(上界)

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

最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

实例1：

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

F(N)=2*N+10

复杂度：O(N)

实例2：

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

F(M,N)=M+N

复杂度：O(M+N)

实例3：

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

F=100

复杂度：O(1)

实例4：

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );

复杂度：O(N) （最坏的预期，N是字符串的长度）

注：

1.strchr函数

参数：

const char *string：一个字符串的首字符地址

int c：要在字符串中找的字符

返回：

返回在字符串中第一次出现字符c是其第几个字符，如果没有找到则返回NULL

实例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;
 }
}

注：

1.这是一个冒泡排序法，如果每一次都需要交换，因此第一次交换N-1次，第二次交换N-2次，一直运行到倒数第二次交换2次，最后一次交换1次，这是一个等差数列，因此F(N)=(N-1+1)*(N-1)/2，这是最差的情况。如果已经有序了再用冒泡排序进行排序，从前往后两两比较，到最后发现不需要交换则break，因此F(N)=N-1

?2.冒泡排序F(N)= $N^{2}$ ，因此复杂度为O( $N^{2}$ )

实例6：

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x) 
{
 assert(a);
 int begin = 0;
 int end = n;
 while (begin < end)
 {
 int mid = begin + ((end-begin)>>1);
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid;
 else
 return mid;
 }
 return -1; }

注：

最好的情况：第一次就找到即时间复杂度为O(1)

最坏的情况：找不到。二分查找本质上其实是逐渐缩短查找的范围，直到还剩一个元素为止，设总共有N个元素，每除以一个2，就查找了一次；反过来看，如果我们找了x次，那么总共有N=1*2*2......*2（x个2）= $2^{x}$ 个元素，那么x= $log_{2}^{N}$ ，因此时间复杂度为O( $log_{2}^{N}$ )，在时间复杂度里面通常会把?O( $log_{2}^{N}$ )简写成?O( $log^{N}$ )

2.该代码是左闭右开的，也就是begin = 0，begin指向的是第一个元素，end = n，end指向了最后一个元素再后面的位置，如下图所示，那么后面都要保持左闭右开，当a[mid] < x时，begin = mid+1，当a[mid] > x时，?end = mid

当代码是左闭右闭的，也就是begin = 0，begin指向的是第一个元素，end = n-1，end指向了最后一个元素，那么后面都要保持左闭右闭，当a[mid] < x时，begin = mid+1，当a[mid] > x时，?end = mid-1，并且while (begin <=end)循环判断中应该是小于等于符号

如果不保持前后一致就有可能出现找不到或者死循环的情况

3.begin + ((end-begin)>>1：这种写法是为了防止begin+end计算的结果在除以2之前就溢出，其中>>1相当于除以2

4.我们要准确分析算法时间复杂度，一定要去看思想，不能只去看程序是几层循环

实例7：

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

复杂度：O(N)

注：

1.从N开始N,N-1,......,2,1,总共递归了N次，所以复杂度：O(N)

2.如果将上面代码改写如下，那么当为N时，里面循环N次，当为N-1时，里面循环N-1次，以此类推，F(N)= $N^{2}$ + $(N-1)^{2}$ +......+ $2^{2}$ + $1^{2}$ ,复杂度为O( $N^{2}$ )

?3.递归算法时间复杂度计算：

（1）每次函数调用是O(1),那么就看他的递归次数

（2）每次函数调用不是O(1),那么就看他的递归调用中次数的累加

实例8：

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N) 
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

复杂度：O( $2^{N}$ )

注：

1.这是一个斐波那契数列，假设每一层全满的情况下，第一层计算1个，第二层计算2个，第三层计算4个，第四层计算8个，依次类推，直到最后N-1层计算 $2^{N-2}$ 个（看这个斐波那契数列最左边的一个分层，第一个数是N，往下分解最左边为N-1......往下分解最后为2，从2到N总共有N-1个数，所以有N-1层）（真是情况下最后几层是不会全满的，因此要减一些，但是从整体上来看是可以忽略的）

F(N)=1+2+4+8+......+ $2^{N-2}$

复杂度：O( $2^{N}$ )?

2.从这里我们可以看出，如果斐波那契数列用这种方法写其实效率是很低的

3.长整型打印用%lld

3.空间复杂度

4. 常见复杂度对比

5. 复杂度的oj练习

5.1.消失的数字

题目链接：面试题 17.04. 消失的数字 - 力扣（LeetCode） (leetcode-cn.com)

?思路：

1.排序+暴力查找/二分查找：? 冒泡排序复杂度O( $N^{2}$ )? ? ? ?qsort快速排序复杂度O( $N\times log^{N}$ )? 因此不能进行排序

2.映射方式：开一个大小为n+1的数组，数组下标从0到n，将数组全部元素初始化为-1，先遍历一遍nums数组，将数组nums中的元素对应到新开的数组中（nums中元素大小与对应到的新数组下标相同）；然后遍历一遍新开的数组，找到数组中-1对应的下标即可。该方法F(n)=2n，时间复杂度为O(n)，符合题目要求

3.异或方式：用一个变量val初始化为0（val和val进行异或结果为0，因此可直接初始化为0），将val跟0~n的数字异或，再跟nums数组中每个元素异或，最后的val结果就是缺失的数字

4.等差数列公式：首先将1到n的n个数加起来（ 1+2+3+......+n=((1+n)*n)/2 ），然后求和的结果减去nums中所有的数即可

[数据结构与算法]数据结构-第1节- 算法的时间复杂度和空间复杂度

1.算法效率

1.1.如何衡量一个算法的好坏