时间复杂度和空间复杂度的计算_时间复杂度(n+2)^3

时间复杂度：执行一个算法，代码运行的次数和问题规模之间的函数关系，用O（）表示。
O（1）：常数项，和问题的规模无关。
时间复杂度计算规则：1.只保留最高阶项 2.不要系数

空间复杂度：执行一个算法，需要额外的辅助空间和问题规模之间的函数关系，用O（）表示。

简单来说，时间复杂度指的是运行次数，空间复杂度指的是浪费了多少内存。

有关于时间复杂度与空间复杂度的例子以及计算方法：
例1.

   for(i=1;i<=n;++i)     //1
      for(j=1;j<=n;++j)   //2
        {
         c[i][j]=0;              //3
         }
1
2
3
4
5

1:n次 2：n+n+n+n+…+n = n的平方 3：n的平方 ，等同于2
所有的加起来f(n)=n+2n^2 = 2n^2
由于计算机的计算机速度很快就把常量系数丢掉了。
因为随着n的增大，n的系数就不要了，因为如果n为100万则系数为1000时，相对于100万来说，1000就很小了，所以就不要了。
所以例1的时间复杂度为：O(f(n))=O(n^2)
空间复杂度为O(1),因为它除了用自身的数组外并没有耗费额外的空间，所以它的空间复杂度为O(1),表示的只是一个常数项的意思，与其问题的规模无关。

例2：

 for(i=1;i<=n;++i)        //1
    for(j=1;j<=n;++j)     //2
    {
         c[i][j]=0;             //3
         for(k=1;k<=n;++k)       //4
          c[i][j]+=a[i][k]*b[k][j];      //5
     }
1
2
3
4
5
6
7

例2 的时间复杂度为：O(f(n))=O(n^3)
空间复杂度为:O(1)
1:n次 2：1每进行一次则2为n次 3：2每进行一次则3为n次 4：2每进行一次则4为n次 5：2每进行一次则5为n次
则根据分析 1为单独n次循环，2和3为1每进行一次为n次循环，４和５为２每进行一次为ｎ次循环 。则时间复杂度为ｎ＋ｎ＾２＋ｎ＾３；
只取最高项所以时间复杂度为n＾３.

依然没有用到额外的辅助空间所以空间复杂度为Ｏ(1) .

例3：

{++x;s=0;}
1

空间复杂度:O(1)
时间复杂度为：f(n)=2*1=2 O(f(n))=O(1):常数项

例4：

for(i=2;i<=n;++i)
    for(j=2;j<=i-1;++j)
    { ++x;a[i][j]=x;}
1
2
3

i为2的时候…0次
i为3的时候…1次
i为4的时候…2次
。。。。。。。。
i为n的时候…n-2次
相当于n*(n-2)! , 2*(1+2+3+…+n-2)=(n-1)*(n-2)=n^2-3n+2
时间复杂度为：n *（n^2） 所以为O(n^3) , 空间复杂度为O(1).

例5：

for(i=1;i<n;i*=2)
{  }
1
2

例5的时间复杂度为O(log2n) ,2为底数。
分析：该for循环的结果为1，2，4，8，16，32…n ,它的运算相当于1 * 2 *2 *2 *…=n 则换算过来就是2^x=n -->也就是x=log2n=logn (2为底数）

递归时间复杂度：

int Fun(int n)
{
   if(n<=1)
     return n;
  else
     return Fun(n-1)+1；
｝
1
2
3
4
5
6
7

算一次的时间为C，则为Cn,回来又一个过程则总时间为2Cn,则时间复杂度为O(n),空间复杂度为O(n)：每一次用一个额外的空间储存Fun(n)循环n次，每一次都要保存不同的值，则用到的空间为n个

当吧return Fun(n-1)+1改为 return Fun(n-2)+1时，影响不大，则时间复杂度和空间复杂度没变。

但当把Fun(n-1)+1改成Fun(n/2)+1; 则其时间复杂度为：log2n (2为底数），空家复杂度为：O(log2n) ， (2为底数）.

最不适合用递归，并且时间复杂度很复杂的例子：（菲波拉切数列）

#include<stdio.h>
int Fibno(int n)
{
  if(n==1 || n==2)
   {
     return 1;
     }
     else
     {
       return Fibno(n-1)+Fibno(n-2);
      }
    }
    int main()
    {
    printf("%d\n",Fibno(42));
    return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这个代码的结果如下图：

这个代码运行的时候会发现光标一闪一闪的会让人以为是形成了死循环，但事实上并不是的，只是因为这个用递归造成时间复杂度比较大，运行的时间久而造成的。