首先我们要知道学习数据结构时都会讨论到算法，数据结构中的问题多数都有算法解决，两者是你中有我，我中有你的关系，所以在数据结构中的学习中算法也是必不可少的。

为方便阅读，以下为本片目录

目录

1.算法效率

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

1.2算法的复杂度

2.时间复杂度

 2.1 时间复杂度的概念

应用题

1.算法效率

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

我们用我们所学过的函数的递归中的一道题来引出今天所要分享的内容

如下是关于斐波那契数列用函数递归的方法实现

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

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

1.2算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。我们今天要研究的是时间复杂度方面的问题

假如我们将冒泡排序分别在一台i3的cpu的电脑上，内存只有1g，和一台i9的cpu的电脑上，内存有16个g的电脑，很显然后者的运行时间更短，运行速度也更快，所以影响到时间复杂度不只是有代码本身，还有运行代码的硬件环境有关。

2.时间复杂度

 2.1 时间复杂度的概念

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

我们接下来一一举例说明。

实例1

请计算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);
}

我们要要计算运行了多少次，不妨将次数设为N

我们观察到第一个for循环是嵌套的形式，所以不难看出一共运行了N*N次；

我们再看第二个for循环，不难看出在第二个表达式中运行了2*N次；

再观察最后一个表达式，不难看出while循环执行了十次；

所以他的时间复杂度函数式：F（N）=N*N+2*N+10

但是在实际问题中我们关注关于时间复杂度的问题重点并不是看它算了多少次，而是将这些次数分成等级，我们关注的是他在时间复杂度中的等级。

就像我们所说的亿万富翁，千万富翁，百万富翁一样，我们根本不需要知道他们的总资产有多少，而是根据这些级别就可以知道这些人的地位。所以在时间复杂度中我们不用关心它具体的运算次数，而是看这些复杂度中划分的等级。

所以在这里我们用大O表示渐进表示法，对他们进行估算。

那么上面的时间复杂度函数式F（N）=N*N+2*N+10我们对他估算时要看哪一项呢？我们带值进去看看

N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010

我们发现N*N这一项对整个公式的结果影响最大，当N越大时对最后的结果最小，如果N无限大时，后面的数基本上都可以忽略不计，所以我们在估算时不妨只看最大项。

所以我们将这个代码的时间复杂度函数式可以表达为：O(N^2)

实例2

int main()
{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);}return 0;
}

可以再想想这样的时间复杂度表达式是什么呢？

是的，答案是O(M+N)

在这个表达式中有两个变量分别是M和N，这两个变量我们都要注意到，我们不可能只在乎N的值，而不在乎M的值，两个变量之间是没有联系的，这里的时间复杂度是O(M+N)。

实例3

void Func4(int N){int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\\n", count);}

可以继续猜测一下这里的时间复杂度表达式是什么

结果是O(1)；而不是O(100)

在这里我们需要注意的是给了一个参数N，但是在函数体中没有用到，那为什么时间复杂度是O(1)呢？

首先我们要清楚我们所要估算的是时间复杂度，O(1)不代表只计算一次，而是代表计算的是常数次，也代表他的计算时间是一个固定值；所以在上面的for循环中，表达式2的上限只要是一个确定的常数，那他的时间复杂度就是O(1),不管他放了多大的数字，这里的时间复杂度都是O(1)。

那为什么呢？答案是因为我们现在电脑所使用的CPU非常强大，运算能力非常强，眨眼的功夫就可以计算几十亿次，在CPU眼里，我们所写的常数次的运算都是渣渣，所以只要我们写常数运算，他的时间复杂读都是O(1).

实例4

再来看下面的这个例子

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);}

通过上面的几个简单的实例来观察这个实例，我们可以把后面是个循环省略掉，那就只剩for循环中的2*N了，那他的时间复杂度就是2*N吗？

答案是，他的时间复杂度还是O(N);

因为2*N中N前面的系数也可以省略掉。我们想象一下，当N无限大的时候，N和2N甚至是5N、100N时前面的系数都是没有意义的，N已经是无限大了，所以我们在估算他的时间复杂度时，还是记作O(N);

实例5

接下来我们加一点难度 

计算strchr的时间复杂度

const char * strchr ( const char * str, int character );

其实也非常的简单，它大致的写法如下

while (*str){if (*str = character)return str;else++str;}

这串代码的意思就是想要在一串字符串中找到我们想要的字符，也就是要遍历字符串。

关于寻找字符这件事是一件不确定的事，我们想要的字符可能出现在字符串的开头，也可能出现在字符串的结尾，这样寻找字符就变成了一件碰运气的事，这样看来他的时间复杂度也是不能够确定的，我们将它分为三种情况，最好、最坏和平均年情况。

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

最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到

也就是说可能是常数次就可以找到我们想要的字符，也有可能在字符串的末尾才能找到，

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

因为我们也无法确定在什么时候找到，所以我们要更加保守的计算，要有底线思维，这样可以降低我们的预期，让我们做最坏的打算。

实例6

难度继续提升

我们不妨来看看之前学过的冒泡排序的时间复杂度

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

冒泡排序相信大家都非常的熟悉，那他的时间复杂度是怎样的呢?

我们可以回想一下冒泡排序是怎样比较并排序的呢？

是一个数和相邻的数进行一次比较，并确定他的位置。要确定一个数的位置，要将所有的数都与他比较，所以如果有N个数，第一个数要比较N-1次才能确定他的位置；第二个数就是N-2次才能确定他的位置，以此类推N-3、N-4、………… 3 、2、1我们会发现比较的次数是一个等差数列，等差数列就有公式：首相加末项乘以项数除以2，这样想我们的公式就是N*（N-1）/2。

通过上面的公式我们会发现最高阶的项还是N*N，也就是N^2,除以2可以看作乘以1/2，前面说到的系数也可以忽略不计，所以时间复杂度就是O(N^2)

实例7

我们不妨继续加上一点难度，来观察一下二分查找的时间复杂度是多少

int BinarySearch(int* a, int n, int x){assert(a);int begin = 0;int end = n - 1;// [begin, end]：begin和end是左闭右闭区间，因此有=号while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid - 1;elsereturn mid;}return -1;}

首先我们要明白二分查找是怎么实现的。

二分查找是不断地缩小区间来查找目标，要算时间复杂度依然要最坏的打算。

第一次查找不到时会将范围缩小至一半，继续查找；如果第二次查找不到，继续讲范围缩小一半，继续查找，就这样以此类推，每次将查找到范围除以2

每找一次就除以2，我们不妨理解为找了多少次，就除以多少次2

那假设找了X次，就除了X次2，我们反过来看就是2^X=N,

X=log2  N

所以二分查找的时间复杂度就是O(log2  N),希望大家能够理解。

了解完二分查找的时间复杂度后我们不妨再和之前的暴力查找进行对比。

我们上面说提到的顺序查找的时间复杂度是O(N),而二分查找的时间复杂度是O(log2  N)，二者再时间上的差异还是很大的，我们可以给N带入具体的数值。

加入我们有一百万个数据交给暴力查找和二分查找，暴力查找要计算一百万次，而二分查找仅仅计算20次即可；

我们通过计算器就可以看到二分查找在计算20次时已经查找了一百万多次的数据，我们以后还需要学很多的数据结构和算法，他们都有不同的使用场景和环境，希望大家可以理解以上的实例。

实例8

我么继续为大家分享几个例子

long long Fac(size_t N){if (0 == N)return 1;return Fac(N - 1) * N;}

我们继续观察上方的代码时间复杂度是多少呢？

需要注意的是这个代码中没有了循环的使用，取而代之的是函数递归，所以时间复杂度是O(N)。

我们会发现如果是调用函数的话，就不难发现F(N-1)就会调用F(N-2),F(N-2)又会调用F(N-3),就这样以此类推，直到调用到最后的F(0)，最后得出结果。

这样的每次调用就会发现调用N次就可以结束，递归不能只考虑当前函数，还需要考虑函数中的子函数，所以他的时间复杂度就是O(N);

实例9

了解上述内容之后我们不妨再加深一点难度

long long Fac(size_t N){if (0 == N)return 1;for(size_t i=0;i<N;i++){//.....}return Fac(N - 1) * N;}

我们就在刚刚的代码中加上一个for循环，这样还能发现时间复杂度吗？

在这里我们每调用一次函数就要将调用的时间加起来，因为所消耗的时间都是相加的，也可以理解为一个等差数列；

我们再来观察for循环中的N，和下面的函数i递归是一样的，N是不断变化的，所以每次循环的次数我们都要加起来，同样也可以看作一个等差数列，所以我们上面所说的等差数列的时间复杂度就是O(N^2);

应用题

了解完以上实例后我们不妨做一道题再来了解一下时间复杂度

面试题 17.04. 消失的数字 - 力扣（LeetCode）

以上是题目链接

首先我们得要确定解题思路：

第一种方法：首先是排序，依次查找，如果下一个数不是上一个数+1的值，那么上一个数+1就是消失的数字

在这里使用qsort来将这个数组排序，qsort的时间复杂度就是O(N*log2  N);

寻找也需要花费时间，那寻找数字的时间复杂度就是O(N)

我们将其合并起来总共花费的时间就是O(N*log2  N+N)

但是我们需要注意的是可以将后面的+N省略掉，对整个式子影响最大的还是前面的那一项。

第二种方法：可以通过两个数相互异或的方法，相异为1，相同为0，两个相同的数字异或就无了，所以我们可以设消失的数字为x，并使x=0；因为0和任何数相异或都为任何数，然后只需要用循环来控制这个全部的遍历的异或，用循环控制就可以使这个时间复杂度为O(N);

int missingNumber(int* nums, int numsSize){int x=0;for(int i=0;i<numsSize;++i){x^=nums[i];}for(int i=0;i<numsSize+1;++i){x^=i;}return x;}

 那我们就选择用异或的方式来解决问题，相信大家能够理解。

以上就是本片要分享的关于时间复杂度的内容，希望大家有所收获，如果对你有帮助不妨三连支持一下，感谢您的阅读。