美文网首页
数据结构基础--时间复杂度和空间复杂度

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

作者: HardCabbage | 来源:发表于2020-06-12 11:24 被阅读0次

时间复杂度:

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)。

相关文章

  • 数据结构与算法 复杂度分析

    复杂度:时间复杂度和空间复杂度。复杂度的分析是学习数据结构与算法的基础! 极简概述 复杂度的分析已经有很多很好...

  • 数据结构学习大纲

    第一章 绪论 数据结构基本概念数据结构基本概念算法的基本概念算法的时间复杂度与空间复杂度分析基础时间复杂度分析空间...

  • 算法复杂度

    数据结构: 数组、链表、栈、队列、二叉树、hash表、图。 空间复杂度和时间复杂度的算法 空间复杂度和时间复杂度 ...

  • 《恋上数据结构与算法一》笔记(二十)总结

    目录 复杂度 线性数据结构 树形数据结构 线性+树形数据结构 一 复杂度 时间复杂度 空间复杂度 二 线性数据结构...

  • 数据结构与算法之线性表

    前言 上一篇《数据结构和算法之时间复杂度和空间复杂度》中介绍了时间复杂度的概念和常见的时间复杂度,并分别举例子进行...

  • 一位算法工程师的自我修养

    数据结构与算法 基本算法思想动态规划贪心算法回溯算法分治算法枚举算法 算法基础 时间复杂度 空间复杂度 最大复杂度...

  • 数据结构(一)时间复杂度

    简介:如果想对数据结构和算法有基本的了解和认识,那么算法复杂度是前提,算法复杂度包含时间复杂度和空间复杂度,具体概...

  • Python-100天(二)-Python语言进阶

    数据结构和算法 算法:解决问题的方法和步骤 评价算法的好坏:渐近时间复杂度和渐近空间复杂度。 渐近时间复杂度的大O...

  • 排序算法

    数据结构8种排序时间和空间复杂度对比七大查找算法学了这么多年算法,你还不知道时间复杂度和空间复杂度如何计算吗?排序...

  • 程序员必须掌握的核心算法有哪些?

    一、算法最最基础1、时间复杂度 2、空间复杂度 一般最先接触的就是时间复杂度和空间复杂度的学习了,这两个概念以及如...

网友评论

      本文标题:数据结构基础--时间复杂度和空间复杂度

      本文链接:https://www.haomeiwen.com/subject/zacgtktx.html