计算程序的时间和空间复杂度

写在前面：\(log_2n\)均记作\(logn\)，实际上在计算机中，\(lnx,lgx\)和\(log_2x\)数值一致，因为：
\[ log_ab=\frac{log_ca}{log_cb} \]

所以：
\[log_2x=\frac{lnx}{ln2}=lnx(\lim\limits_{x\to+\infty})\]

\[log_2x=\frac{lgx}{lg2}=lgx(\lim\limits_{x\to+\infty})\]

一、时间复杂度

（一）概念

如果一个问题的规模是\(n\)，解这一问题的某一算法所需要的时间为\(T(n)\)，它是\(n\)的某一函数，\(T(n)\)称为这一算法的“时间复杂性”。

当输入量\(n\)逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”，也可以表示为时间复杂度。时间复杂度是总运算次数表达式中受\(n\)的变化影响最大的那一项（不含系数）。

“大\(O\)记法”：在这种描述中使用的基本参数是\(n\)，即问题实例的规模，把复杂性或运行时间表达为\(n\)的函数。这里的“\(O\)”表示量级 \((order)\)，比如说“二分检索是\(O(nlogn)\)的”,也就是说它需要“通过量级\(logn\)的步骤去检索一个规模为\(n\)的数组”记法，表示当\(n\)增大时，\(O(f(n))\)运行时间至多将以正比于\(f(n)\)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的\(O(n^2)\)算法在\(n\)较小的情况下可能比一个高附加代价的\(O(nlogn)\)算法运行得更快。当然，随着\(n\)足够大以后，具有较慢上升函数的算法必然工作得更快。

计算时间复杂度的关键因素：循环次数和递归次数

（二）针对几个程序的时间复杂度

\(O(1)\)

temp=i;i=j;j=temp; 

我们经常会听到大佬们说：“使用\(O(1)\)的查询...”，实际上就是与\(n\)无关，只是在进行语句。

\(O(n)\)

例子1

1 sum=0；
2 for(i=1;i<=n;i++) {
3 for(j=1;j<=n;j++) {
4 sum++；   }
5 }

第1行：\(1\)次

第1行：\(n\)次

第1行：\(n^2\)次

第1行：\(n^2\)次

解：\(T(n)=2n^2+n+1 =O(n^2)\)

以上是求解程序正常的时间复杂度的方法，即忽略\(T(n)\)中\(n\)的最高次项的系数和其他项（宗旨是只考虑最大项）

（此处想到了物理老师，当\(m<<M\)的时候，表达式\(a=\frac{M}{M+m}g\)忽略\(m\)的取值 即\(m\)微小到不对结果起到作用）

例子2

for (i=1;i<n;i++) {
    y=y+1;         ①
    for(j=0;j<=(2*n);j++)   {
    x++; }       ②
}   

解：
语句1的频度是\(n-1\)

语句2的频度是$(n-1)*(2n+1)=2n^2-n-1 $

$f(n)=2n^2-n-1+(n-1)=2n^2-2 $

该程序的时间复杂度\(T(n)=O(n^2)\)

\(O(logn)\)

i=1;       ①
while (i<=n)
    i=i*2; ②

解： 语句1的频度是1

设语句2的频度是\(f(n)\), 则：$2^{f(n)}\leq n;f(n)\leq logn $

取最大值\(f(n)=logn, T(n)=O(logn )\)

\(O(n^3)\)

 for(i=0;i<n;i++)
    {
       for(j=0;j<i;j++)
       {
          for(k=0;k<j;k++)
             x=x+2;
       }
    }

解：当\(i=m, j=k\)的时候,内层循环的次数为\(k\)

当\(i=m\)时,\(j\)可以取 \(0,1,…,m-1\) ,

所以这里最内循环共进行了\(0+1+…+m-1=\frac{(m-1)m}{2}\)次

所以,\(i\)从\(0\)取到\(n\), 则循环共进行了:\(0+\frac{(1-1)\times 1}{2}+…+\frac{(n-1)n}{2}=\frac{n(n+1)(n-1)}{6}\)

所以时间复杂度为\(O(n^3)\)

（三）一些特殊的时间复杂度

1. 时间复杂度的不稳定性

我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最坏情况运行时间是$ O(n^2)\(，但期望时间是\) O(nlogn)\(。通过每次都仔细地选择基准值，我们有可能把平方情况 (即\)O(n^2)\(情况)的概率减小到几乎等于\) 0$。在实际中，精心实现的快速排序一般都能以 \(O(nlogn)\)时间运行。

1. 一些常用的记法：

(1) 访问数组中的元素是常数时间操作，或说\(O(1)\)操作。

(2) 一个算法如果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 \(O(logn)\)时间。

(3) 用\(strcmp\)比较两个具有\(n\)个字符的串需要\(O(n)\)时间。

(4) 常规的矩阵乘算法是\(O(n^3)\)，因为算出每个元素都需要将\(n\)对元素相乘并加到一起，所有元素的个数是\(n^2\)。

(5) 指数时间算法通常来源于需要求出所有可能结果。例如，\(n\)个元素的集合共有\(2n\)个子集,所以要求出所有子集的算法将是\(O(2^n)\)的。

指数算法一般说来是太复杂了，除非\(n\)的值非常小，因为，在这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 \((\)如著名的“巡回售货员问题” \()\)，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果的算法替代之。

计算方法

一般情况下，算法的基本操作重复执行的次数是模块\(n\)的某一个函数\(f(n)\)，因此，算法的时间复杂度记做：\(T(n)=O(f(n))\)。随着模块\(n\)的增大，算法执行的时间的增长率和\(f(n)\)的增长率成正比，所以\(f(n)\)越小，算法的时间复杂度越低，算法的效率越高。

在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出\(T(n)\)的同数量级（它的同数量级有以下：\(logn,n,nlogn,n^2,n^3,2^n,n!\)），找出后，\(f(n)=\)该数量级，若\(\frac{T(n)}{f(n)}\)求极限可得到一常数\(c\)，则时间复杂度\(T(n)=O(f(n))\)。

1. 常见的时间复杂度

按数量级递增排列，常见的时间复杂度有：常数阶\(O(1)\), 对数阶\(O(logn)\), 线性阶\(O(n)\), 线性对数阶\(O(nlogn)\), 平方阶\(O(n^2)\)， 立方阶\(O(n^3)\),…， \(k\)次方阶\(O(n^k)\), 指数阶\(O(2^n)\) 。

其中，

1.\(O(n)\)，\(O(n^2)\)， 立方阶\(O(n^3)\),…，\(k\) 次方阶\(O(n^k)\) 为多项式阶时间复杂度，分别称为一阶时间复杂度，二阶时间复杂度……

2.\(O(2^n)\)，指数阶时间复杂度，该种不实用

3.对数阶\(O(logn)\), 线性对数阶\(O(nlogn)\)，除了常数阶以外，该种效率最高

例：算法：

 for（i=1;i<=n;++i）
  {
     for(j=1;j<=n;++j)
     {
         c[i][j]=0; //1

          for(k=1;k<=n;++k)
               c[i][j]+=a[i][k]*b[k][j]; //2
     }
  }

1:该步骤执行次数：\(n^2\)

2:该步骤执行次数：\(n^3\)

则有$ T(n)= n^2+n^3\(，根据上面括号里的同数量级，我们可以确定\) n^3\(为\)T(n)$的同数量级

则有\(f(n)= n^3\)，然后根据\((\lim\limits_{n\to+\infty})\frac{T(n)}{f(n)}\)求极限可得到常数$c $

则该算法的 时间复杂度：\(T(n)=O(n^3)\)

重要：

\(O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<...<O(n^k)<O(2^n)<O(n!)\)

（以下方法来自网络，仅供参考）

练习：请计算出以下程序的时间复杂度\(O(k)\)

#include <cstdio>
using namespace std;
int a[100],b[100];
int k;
int main(){
    for(int i=0;i<10;i++){//1
        a[i]=i+1;
    }
    for(int i=0;i<10;i++){//2
        for(int j=0;j<a[i];j++){//3
            b[k]=a[i];
            k++;
        }
    }
    for(int i=0;i<k;i++){//4
        if(i==0){
            printf("%d",b[i]);
        }
        else{
            printf(",%d",b[i]);
        }
    }
    return 0;
}

二、空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，用$ S(n)$ 来定义。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做\(S(n)=O(f(n))\)。比如直接插入排序的时间复杂度是\(O(n^2)\),空间复杂度是\(O(1)\) 。而一般的递归算法就要有\(O(n)\)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

空间复杂度比较常用的有：\(O(1)\)、\(O(n)\)、\(O(n^2)\)：

1. 空间复杂度$ O(1)$

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 \(O(1)\)

举例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 $i,j,m $所分配的空间都不随着处理数据量变化，因此它的空间复杂度 \(S(n) = O(1)\)

1. 空间复杂度\(O(n)\)

我们先看一个代码：

int n=1000;
int new[n];
for(i=1; i=n; ++i)
{
   j = i;

   j++;
}

这段代码中，第一行\(new\)了一个数组出来，这个数据占用的大小为\(n\)，这段代码的\(2-6\)行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 \(S(n) = O(n)\)

\(125MB=131072000B\approx10^8B\)

\(int\)	2
$long $ \(long\)	4
\(unsigned\) $ long$ \(long\)	8
\(float\)	4
\(double\)	8
\(long\) \(double\)	16
\(bool\)	1

计算方法：

如果开了\(n\)个不同类型的数组，每个类型开了\(d_i\)个，则一共有$n_t=\sum_{i=1}^{n}d_i \(，每个类型所占字节为\)p_i\(，每个类型的每个数组大小为\)y_{i_j}(j\in[1,d_i],i\in[1,n])$

程序最大空间为\(P\) \(MB\) \(=1048576P\) \(B=C\) \(B\)

对于\(S=\sum_{i=1}^{n}\lbrack \sum_{j=1}^{d_i}(p_i*y_{i_j})\rbrack\leq C\)满足条件，即符合

举例：
三个数组，\(bool[1000],int[20000],double[300000]\)

则\(S=1\times1000+2\times20000+8\times3000000=24041000>13107200\)

所以空间复杂度不符合

2019.11.28