首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法的复杂性详解及原理

算法的复杂性详解及原理

作者头像
MickyInvQ
发布2022-10-28 10:05:06
4170
发布2022-10-28 10:05:06
举报
文章被收录于专栏:InvQ的专栏InvQ的专栏

文章目录

14天阅读挑战赛 *努力是为了不平庸~ 每个学习算法的都需要一把打开算法的钥匙,就如陶渊明的《桃花源记》中 ”初极狭才通人,复行数十步,豁然开朗“。

算法知识点

算法的特征

  • (1)有穷性:算法是由若干条指令组成的有穷序列,总是在执行若干次后结束,不可能永不停止。
  • (2)确定性:每条语句都有确定的含义,无歧义。
  • (3)可行性:算法在当前环境下, 可以通过有限次运算来实现
  • (4)输入/输出:有零个或多个输入,以及一个多或多个输出。

算法题目描述

写一个算法,求一下序列之和:

在这里插入图片描述
在这里插入图片描述

做题思路

当你看到这个题目的时候,你会怎么想?for循环?while循环? 先看for循环的代码

for循环解决

int sum1(int n){
   int sum=0;
   for(int i=1;i<=n;i++)
      sum+=pow(-1,i);//表示(-1)^i 
   return sum;
}

上面这段代码,确实可以实现求和运算,但是为什么不这样算呢?

在这里插入图片描述
在这里插入图片描述

再看另一种写法:

归纳法解决

int sum2(int n){
   int sum=0;
   if(n%2==0)
      sum=0;
   else
      sum=-1;
   return sum;
}

看到这段代码后,是不是恍然大悟,原来还可以这样啊,这不就是数学家高斯使用的算法吗?

在这里插入图片描述
在这里插入图片描述

一共50对数,每对数的和均为101,因此总和为:

(1+100)* 50 = 5050

1787年,10岁的高斯用了很短的时间就算出了结果,而其他小孩子用了半天。 可以看出,使用for循环的话,需要循环n次,每次循环内还要pow运算,然后再相加运算。如果n = 10000,那么就算运算 10000次这样的过程。而通过我们观察归纳,第二种方式,只需要1次,是不是有很大的差别?

高斯的方法我也知道,但是遇到类似的问题…我们用的笨方法也是算法吗? 答:是的

算法复杂度的计算

好算法的标准

  • 高效 - 时间复杂度
  • 低存储 - 空间复杂度

时间复杂度的计算

算法运行需要的时间,现代计算机,一秒能运算很多次,所以不能用秒来计量。相同计算机一次时间相对固定,不同配置的计算机又不相同。所以我们将执行次数作为时间复杂度。

int sum=0;                  //运行1次
int total=0;                //运行1次
for(int i=1;i<=n;i++){      //运行n+1次,最后一次判断不满足循环条件
  sum=sum+i;                //运行n次
  for(j=1;j<=n;j++)         //运行n×(n+1)次
    total=total+i*j;        //运行n×n次
}

如果把上面的所有语句的运行次数加起来:

1 + 1 + n+1 + n + n×(n+1) + n×n 。

这个可以用一个函数T(n) 来表示: T(n) = 2n2+3n+3 当n足够大的时候,例如n = 105 ,那么T(n) = 2 * 1010 + 3 *105 +3 可以看出,算法运行的时间主要取决于最高项,小项和常数可以忽略不计。 有些算法,如排序,查找、插入算法等,可以分为最好最坏平均情况分别去求算法的渐进复杂度。但是考察一个算法时,通常考察最坏的情况,最坏的情况对衡量算法好坏具有实际意义

空间复杂度的计算

算法占用的空间大小。 空间复杂度的本意指的是算法在运行过程中,占用了多少存储空间。算法占用的存储空间包括:

  • (1)输入、输出数据
  • (2)算法本身
  • (3)额外需要的辅助空间 输入输出占用的空间是必须的,算法本身占用的空间可以通过精简算法来缩减,但缩减的量是很小的,可以忽略不计。 算法在运行时候,所使用的辅助变量占用空间,才是衡量算法复杂度的关键因素。
常数变量复杂度

请分析如下的算法空间复杂度

void swap(int x,int y){    //交换x与y 
     int temp;
     temp=x;               //temp为辅助空间 ①
     x=y;                  //②
     y=temp;               //③
}

两个数交换的过程:

在这里插入图片描述
在这里插入图片描述

这里使用了temp辅助变量,空间复杂度为O(1)

递归空间复杂度

在递归算法中,每次递归都需要一个栈来保存调用记录,因此在计算递归的空间复杂度的时候,需要计算递归栈的深度。

int fac(int n){ //计算n的阶乘
    if(n==0||n==1) 
        return 1; 
    else 
        return n*fac(n-1); 
}

阶乘是典型的递归调用问题,递归包括地推和回归。递推是将原问题不断分解成子问题,直至满足结束条件,返回最近子问题的解。然后逆向逐一回归,最终到达递推开始的原问题,返回原问题的解。

思考:试求5的阶乘,程序将怎么计算呢? 5的阶乘的递推和回归的过程如下:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

如上面两个图所示,递推、回归过程是从逻辑思维上推理,以图的方式形象的表达出来, 但计算机内部是怎样计算的呢?计算机使用一种称为“栈”的数据结构,“栈”类似放盘子的容器,每次从顶端放进去一个,拿出来的时候就只能从顶端拿,不允许从中间插入或抽取,因此称为“后进先出”

从图中可以看出,进栈,出栈的过程:子问题先被一步步压进栈,直至直接可解得到返回值,再一步步的出栈,最终得到返回值。在运算过程中,因为使用了n个栈作为辅助空间,因此阶乘的递归算法的空间复杂度为O(n)。时间复杂度也为O(n),因为n的阶乘仅比n-1的阶乘多了一次乘法运算,fac(n) = n * fac(n-1)。如果用T(n) 表示fac(n)的时间复杂度,则可以表示为 T(n) = T(n) + 1 =T(n-1) + 1 + 1 … = T(1) + …1 + 1 =n

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2022-10-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 算法知识点
    • 算法的特征
    • 算法题目描述
    • 做题思路
      • for循环解决
        • 归纳法解决
        • 算法复杂度的计算
          • 时间复杂度的计算
            • 空间复杂度的计算
              • 常数变量复杂度
              • 递归空间复杂度
          相关产品与服务
          容器服务
          腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档