记录六时间复杂度和空间复杂度

作者: 筏执 | 来源:发表于2020-02-01 21:49 被阅读0次

两数之和 - Rust
记录六时间复杂度和空间复杂度
时间复杂度和空间复杂度笔记
NLP初学之-算法复杂度
数据结构-0-时间复杂度和空间复杂度
排序算法的时间复杂度和空间复杂度
算法复杂度
算法汇总
算法复杂度之时间复杂度和空间复杂度
漫步数据结构与算法系列之时间复杂度

一个算法的优劣性主要是从时间复杂度和空间复杂度进行衡量的。

时间复杂度的概念

（下面将会以概念和大量习题了解时间复杂度。）

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大 $O$ 符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。【1】

时间复杂度定性的描述着算法的运行时间，但是时间复杂度的计算并不是运行的具体时间，而是算法执行语句的时间。一个算法的执行时间大致上等于其所以语句执行时间的总和，而语句的执行时间则为该条语句的重复次数和执行一次所需时间的乘积。【3】

通常，我们为了计算时间复杂度，会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。但是，相同大小的不同输入值依旧可能会造成算法的运行时间不同，因此，我们通常在计算时间复杂度时，通常使用算法的最坏情况复杂度。记为 $T(n)$ ,定义为任何大小的输入n所需的最大运行时间。另一种较少使用的方法是平均情况复杂度，通常有特别指定才会使用。时间复杂度可以根据T(n)的不同，可以分为线性时间算法和指数时间算法。【1】

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 $T(n)$ 。

语句频度(Frequency Count,又称时间频度)：一条语句的重复执行次数。

(下面分析什么是时间复杂度)

在衡量算法效率的方法中我们知道，有事后统计算法和事前分析估计法。事后统计算法是直接用程序进行测试衡量，而事前分析估计法则是利用统计学的方法进行估计。实际上，我们是无法得到一个算法运行的绝对时间。我们只能估计其算法所需要的时间。因为程序语句在执行时，其执行时间受到软、硬件环境等影响较大。我们无法精确得出算法实际执行所需要的时间。所以，所谓的算法分析并非精确统计算法实际执行所需的时间，而是针对算法语句的执行次数做出统计，从中得到算法执行时间的信息。【3】

举个例子：

（例题1.）求以下算法的执行时间：

for(i=1;i<=n;i++) //外循环

for(j=1;j<=n;j++) //内循环

a[i][j]=0; //执行的语句

如何求解呢？

我们先设算法的每条语句在执行一次所需要的时间均为单位时间。单位时间为1；

则再计算语句频度。首先外循环将会执行n+1次，而内循环因为受到外循环的影响，内循环所执行的次数就是

$n(n+1)$ 。而执行的语句中，受到内外两重循环的影响，其执行的语句所执行的次数就是 $n^2$ 。

则该算法的语句频度就为：(频度指该条语句所执行的次数。)

for(i=1;i<=n;i++) //频度为 $n+1$

for(j=1;j<=n;j++) //频度为 $n(n+1)$

a[i][j]=0; //频度 $n^2$

因为 一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行从次数和执行一次所需时间的乘积。【3】

所以，当我们提前假设每条语句执行一次所需的时间为单位时间时，算法的执行时间其实大致上就为其所以频率之和。所以，该算法的所执行时间为为 $(n+1)+n(n+1)+n^2$ 为 $f(n)=2n^2+2n+1$ 。

是不是很麻烦？我们要统计所有的语句频率才可以计算的算法的大致时间。而且，当我们计算出来后，大部分都是一些复杂的多项式。而我们要比较两个复杂的多项式的大小时，还需要计算。这样会十分麻烦。所以为了更加直白的比较两个算法运算时间。所以，我们通常只用算法中的“基本语句”的执行次数来度量算法的工作量。（“基本语句”：指算法中重复执行次数和算法的执行时间成正比的语句。它对算法的运行时间的贡献最大。）

通常而言，算法的执行时间是随问题规模增长而增长的，因此对算法的评价通常只需要考虑其随问题规模增长的趋势即可。所以，我们为了考虑算法在执行的最坏的情况。我们通常将问题规模趋向于无穷。这时候，我们只需要考虑算法中基本语句的执行次数在渐进意义下的阶。

例如，在例题1中，当n趋向于无穷大时，显然有 $\lim_{n\to0} f(n)/n^2 = \lim_{n\to0} (2n^2+2n+1)/n^2=2$ 。即当n无穷大时， $f(n)$ 与 $n^2$ 之比为一个不为零常数。即表明 $f(n)$ 和 $n^2$ 的数量级（Order of Magnitude）相同。我们使用“ $O$ ”表示数量级。则 $T(n)=O(f(n))=O(n^2)$ 。由此可得时间复杂度的定义。

时间复杂度的定义

一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数 $f(n)$ ,算法的时间量度记作

$T(n)=O(f(n))$

它表示随问题规模n的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同，称作为算法的渐进时间复杂度，简称时间复杂度（Time Complexity）。【3】

数学符号 $O$ 的严格定义为：

若 $T(n)$ 和 $f(n)$ 是定义正整数集合上的两个函数，则 $T(n)=O(f(n))$ 表示存在正的常数 $C$ 和 $n_{0}$ ,使得当 $n\geq n_{0}$ 时都满足 $0\leq T(n)\leq Cf(n)$ 。【3】

数学符号 $O$ 的定义说明了函数 $T(n)$ 和 $f(n)$ 具有相同的增长趋势，且 $T(n)$ 的增长至多趋向于函数 $f(n)$ 的增长。

时间复杂度个人理解（如果不对，请大佬指出。）

(是不是被一大堆数学给搞懵逼了？是的，之前我也是这样的。但是这一次记录让我好像明白了一点点。上面所有的分析证明说明白了几件事。

1.一个算法的执行时间大致上是所有语句执行时间的总和。而语句的执行时间则为该条语句重复执行次数和执行一次所需要的乘积。

2.一条语句的重复执行次数称作语句频度。

3.当设每条语句执行一次所需的时间为单位时间时，该语句的执行时间就是语句频度。

4.在3条的基础上可以得出该算法的执行时间是语句频度之和。

5.因为对于一个算法而言，语句频度是比较难以计算的。而且由语句频度得出来算法的执行时间也是不好比较的。因为都是一些复杂的多项式。

6.为了解决5的问题，我们只需要客观的反应算法的时间复杂度即可。而我们只需要选择一些“基本语句”，这些“基本语句”是指那些对算法的运行时间贡献最大的。对算法的运行时间是不良影响，但是却无可避免。

7，当我们去除一些多余的频度之后，算法的执行时间很大部分上依旧还是一些比较复杂的多项式，所以，我们还得继续简化。我们知道，在一般情况下，算法的执行时间是随则问题规模 $(n)$ 的增长而增长的。所以，我们得从问题规模 $(n)$ 出发。

8.因为问题规模 $(n)$ 的增长，算法的执行时间对增加，所以，我们可以考虑算法的最坏情况，也就是当问题规模 $(n)$ 无限大时，我们只需要考虑算法中基本语句的执行次数的时间在渐进意义下的阶。(什么意思呢，当执行次数为 $f(n)=n^2+2n+1$ 时，随着 $n$ 的增大，对 $f(n)$ 的影响最大的是 $n^2$ ,所以我们只需要关心阶数即可。

9.当问题规模 $n$ 无穷大时，我们可以用数学的极限知识，了解到，当 $n$ 在趋向于无穷时，执行时间 $f(n)$ 与最高阶的数量级是相同的。而数量级我们用 $O$ 表示。所以我们在比较两个算法的执行时间时，我们可以用数量级 $O$ 来比较。

10.时间复杂度的表示算法为 $O(频度)$

求解算法的时间复杂度

求解算法的时间复杂度之前，我们先了解一些常用的时间复杂度。

常数阶 $O(1)$

对数阶 $O(\log_2 n )$

线性阶 $O(n)$

线性对数阶 $O(n\log_2 n )$

平方阶 $O(n^2)$

立方阶 $O(n^3)$

K次方阶 $O(n^k)$ $(K>3)$

指数阶 $O(2^n)$

从上至下，随着n的不断增大，时间复杂度越大，运算所耗费的时间就越高。

计算时间复杂度主要有四步：

1.求出“基本语句”所需要的频数之和。（ $f(n)$ ）。

2.只保留最高次项.例如 $f(n)=3n^3+2n+1$ 变成 $f(n)=3n^3$ 。

3.将最高项系数都化为1.例如 $f(n)=3n^3$ 变成 $f(n)=n^3$ 。(注意：如果只留下了常数的话，其时间复杂度就为 $O(1)$ 。)

4.代入公式 $T(n)=O(f(n))$ 中。例如： $f(n)=n^3$ 带入公式得 $T(n)=O(n^3)$ 。即时间复杂度为 $O(n^3)$ 。

(例题在总结中。)

最好，最坏和平均时间复杂度

对于某些问题的算法，其基本语句的频度不仅仅与问题的规模相关，还依赖与其它因素。

举个例子：【3】

分析下面的时间复杂度。

for(i=0;i<n;i++) //语句1

if (a[i] == e) return i+1; //语句2

return 0; //语句3

首先，我们可以看出，在这个算法中，语句2的频度不仅仅与问题规模 $n$ 有关，还与实例数组 $a$ 的各个元素值以及e的取值有关。

假设 $a[0]==e$ ,则时间复杂度为 $O(1)$ 。

假设数组 $a$ 中没有任何一个数与 $e$ 相等，则时间复杂度为 $O(n)$ 。

这时候，便有了一个最好时间复杂度和一个最坏时间复杂度。

而对于一个算法来说，需要考虑各种可能的出现的情况，以及每一种情况出现的概率。所以，在一般情况下，可以假设查找的元素在数组中所以位置上出现的可能性均相同。这时可以取最好情况和最坏情况的平均值。即 $O(\frac{n}{2} )$ 。即为平均时间复杂度。

称算法在最好情况下的时间复杂度为最好的时间复杂度，指算法计算量可能达到的最小值；称算法在最坏情况下的时间复杂度为最坏时间复杂度，指算法计算量可能达到的最大值；算法的平均时间复杂度是指算法在所有可能下，按照输入实例以等概率出现时，算法计算量的加权平均值。

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

空间复杂度比时间复杂度稍微容易一点。只需要理解了空间复杂度的意思即可。

首先，我们先官方一波。

有关于算法的存储空间需求，类似于算法的时间复杂度，我们采用渐进空间复杂度(Space Complexity)作为算法所需存储空间的量度。简称空间复杂度，它也是问题规模 $n$ 的函数，记作:

$S(n) = O(f(n))$

一般情况下，一个程序在机器上执行时，除了需要寄存本身所用的指令、常数、变量、和输入数据外，还需要一些对数据进行操作的辅助存储空间。其中，对于输入数据所占的具体存储量取决与问题本身，与算法无关。这样，只需要分析该算法在实现时所需要的辅助空间就可以了。

空间复杂度个人理解(如果不对，请大佬指出。)

(对于一个算法而言，所占用的空间一般分为3个。

1.输入的数据空间

2.指令、常数所本身占用的空间(该空间是固定的。一般是按照需求来的。)

3.辅助存储空间。(在执行某些计算时，所借助的临时存储空间。例如，在将两个数据交换时，如果对于一个整数而言，能够保证数据相加相减都不会超过整数的范围之外时，利用相加或者相减法会比借助临时存储空间的空间复杂度要低。

而一般而言，空间复杂度指的是辅助存储空间的大小。如果借助辅助存储空间的大，则空间复杂度就大，反之，空间复杂度就少。所以，注意一下辅助空间的大小即可。))

空间复杂度和时间复杂度的相爱相杀

空间复杂度和时间复杂度是评判算法优劣性的两大衡量点。要评判算法的好坏，时间复杂度和空间复杂度是离不开的，但是，对于一个算法而言，其时间复杂度和空间复杂度往往是互相影响的，当追求一个较好的时间复杂度时，往往需要大量的辅助空间作为缓存，而当追求一个较好的空间复杂度时，往往使得执行语句的次数会变多，从而影响时间复杂度。真的是相爱相杀呀。

（通常，鉴于现如今运算空间较为充足，人们往往以时间复杂度为重。）

总结

时间复杂度和空间复杂度是一个比较抽象的东西了，=-=因为需要一些数学知识。空间复杂度还好，只是这时间复杂度，emmmmm。有点难度。下面个人总结一下时间复杂度以及空间复杂度。然后再做一些习题巩固。

时间复杂度：时间复杂度是指执行算法所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

(时间复杂度取决于算法中基本运算执行的次数，与计算机本身无关。)

计算时间复杂度需要4步。

1.求出“基本语句”所需要的频数之和。

2.只保留最高项。

3.将最高项系数都化为1。(如果只留下了常数，则为时间复杂度为常数阶。)

4.带入公式。

空间复杂度：是对一个算法在运行过程中临时占用存储空间大小的量度。

一般而言，空间复杂度指的是辅助存储空间的大小。

例题：

例题1:设 $n$ 是描述问题规模的非负整数，则下面程序段的时间复杂度为____________。

x=2;

while(x< n/2 )

x = 2 *x;

例题2：下面程序段的时间复杂度是_________。

count=0;

for(k=1; $k\leq n$ ;k*=2)

for(j=1; $j\leq n$ ;j++)

count++;

例题3:以下程序段中语句"x++"的语句频度为___________。

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

for(k=1;k<=j;k++)

x++；

例题4:以下程序段语句中"m++;"的语句频度为________。

int m=0,i,j;

for(i=1;i<=n;i++)

for(j=1;j<=2*i;j++)

m++;

例题5：设一维数组中有 $n$ 给数组元素，则读取第 $i$ 个数组元素的平均复杂度为________。

解答：

例题1:

设程序中基本语句“x=2*x;”执行的次数为K，执行K次时: x=2^(k+1)。由循环结束条件x<n/2可得。2^(k+1)<n/2。即 $k<\log_2 n -2$ , $K=\log_2 n +C$ （C为常数），因此 $T(n) = O(\log_2 n )$ 。

例题2:

外循环:条件为 $k\leq n$ ，增量为k*=2；可以知道循环次数为 $2^k\leq n$ 。即 $k\leq \log_2 n$ 。所以最外层的时间复杂度为 $O(\log_2 n)$ 。

内循环:条件为 $j\leq n$ ，增量为j++;可以找到循环次数为n次，即内层循环的时间复杂度为 $O(n)$ 。

则该程序的时间复杂度为: $T(n)=O(\log_2 n )*O(n)=O(n\log_2 n)$

例题3:

"x+;"的语句频度为: $\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j1=\sum_{i=1}^n\sum_{j=1}^i j=\sum_{i=1}^n \frac{i(i+1)}{2}=\frac{1}{2}(\sum_{i=1}^n i^2+\sum_{i=1}^n i)=\frac{n(n+1)(n+2)}{6}$