数据结构基础--时间复杂度和空间复杂度

时间复杂度：

1，算法的输入时间

2，编译可执行代码时间

3，执行指令的的时间

4，执行重复的命令时间

时间复杂度的计算一般使用大O表示法，在该表示法中的术语包括以下几种：常数阶、线性阶、平方阶、对数阶、立方阶等等，以下是详细解析。

大O表示法：

 1：用常数1取代运行时间中所有的常数3->1

 2：在修改运行次数函数中，只保留最高阶项n^2 +n^4+n^7 -> n^7

 3：如果在最高阶存在且不等于1，则去除这个项目相乘的常数2n^3 -> n^3

1.常数阶：
不管常数是O(1)、O(10)、O(1000)等其他任何数字都记作O(1)，对于分支结构，不管条件真假，程序执行的次数一定是恒定的，只要程序里面是不包含在循环结构中的单纯分支结构，它的时间复杂度就为O(1)。

//1+1+1 = 3 O(1)
void testSum1(int n){
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum1:%d\n",sum);//执行1次
}
//例子
//1+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n){
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum2:%d\n",sum);//执行1次
    
}

2.线性阶：
线性阶比较复杂，要想确定线性阶，首先要确定循环中语句的运行次数，所以我们在分析算法的时间复杂度的时候关键就是确定循环结构的运行次数。下面的这段代码循环次数为n次，所以时间复杂度用大O表示法为O(n)。

//x=x+1; 执行n次 O(n)
void add2(int x,int n){
    for (int i = 0; i < n; i++) {
        x = x+1;
    }
}

//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
    int i,sum = 0;               //执行1次
    for (i = 1; i <= n; i++) {   //执行n+1次
        sum += i;                //执行n次
    }
    printf("testSum3:%d\n",sum);  //执行1次
}

3.平方阶
以下示例是平方阶是双层循环嵌套，内层循环的时间复杂度在线性阶时就已经讲到(n),如果是双层循环的情况下最外层循环n次，那么这段代码的时间复杂度记作O(n^2)。

  for(int i=0;i<n;i++){   
      for(int j=i;j<n;i++){
         //复杂度为O(1)的算法
         ... 
      }
  }
//x=x+1; 执行n*n次 ->O(n^2)
void add3(int x,int n){
    for (int i = 0; i< n; i++) {
        for (int j = 0; j < n ; j++) {
            x=x+1;
        }
    }
}

//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
void testSum4(int n){
    int sum = 0;
    for(int i = 0; i < n;i++)
        for (int j = i; j < n; j++) {
            sum += j;
        }
    printf("textSum4:%d",sum);
    
}

4.对数阶

/*2的x次方等于n x = log2n  ->O(logn)*/
void testA(int n){
    int count = 1;         //执行1次
    //n = 10
    while (count < n) {
        count = count * 2;
    }
    
}
//例子2
int count = 1;
while (count < n)
{    
count = count * 2; /* 时间复杂度为O(1)的程序步骤序列 */
}

在上述例子2中由于每次count乘以2之后，就距离n更近了一分。
也就是说，有多少个2相乘后大于n，则会退出循环。
由2x=n得到x=log2n。所以这个循环的时间复杂度为O(logn)。
5.立方阶
立方阶是三层循环嵌套，内层循环的时间复杂度在线性阶时就已经讲到(n),如果是三层循环的情况下中间层和最外层都循环n次，那么这段代码的时间复杂度记作O(n^3)。

void testB(int n){
    int sum = 1;                         //执行1次
    for (int i = 0; i < n; i++) {        //执行n次
        for (int j = 0 ; j < n; j++) {   //执行n*n次
            for (int k = 0; k < n; k++) {//执行n*n*n次
                sum = sum * 2;          //执行n*n*n次
            }
        }
    }
}

总结常见的时间复杂度

执行次数函数	阶	术语
12	O(1)	常数阶
2n+3	O(n)	线性阶
3n^2+2n+1	O(n^2)	平方阶
5log2n+20	O(logn)	nlogn阶
6n3+2n2+3n+4	O(n^3)	立方阶
2^n	O(2^n)	指数阶

总结：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

空间复杂度

算法的空间复杂度通过计算算法所需要的存储空间实现，算法空间复杂度的计算公式记作：S(n)=n(f(n)),其中n为问题的规模，f(n)为语句关于n所占存储空间的函数。

空间复杂度计算因素

• 寄存器本身的指令
• 常数
• 变量
• 输入
• 对数据进行操作的辅助空间

在考量算法的空间复杂度，主要是考虑算法执行时所需要的辅助空间。

下面用一个例子进行说明

 int n = 5;
 int a[10] = {1,2,3,4,5,6,7,8,9,10};
   //以上不算是辅助空间
    //算法实现(1)
    int temp;//通过辅助空间来做中间的交换
    for(int i = 0; i < n/2 ; i++){
        //O(1)
        temp = a[i];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }

    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[i]);

    }
    

通过辅助空间temp来做中间的交换,时间复杂度为O(1)

//算法实现(2)
    int b[10] = {0};
    for(int i = 0; i < n;i++){
        b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++){
        a[i] = b[i];
    }
    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[i]);
        
    }

现将数组倒数存入一个数组，在顺序存到a中,时间复杂度为O(n)。