数据结构-2算法和时间复杂度

￡神魔★判官ぃ 2022-03-27 12:44 187阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MTEwNTM4_size_16_color_FFFFFF_t_70][]

# 什么是算法？ #

对问题求解步骤的描述，通过有限序列的指令来实现

# 特征： #

1.  有穷性：有限，不重复循环
2.  确定性：每个步骤都是明确无歧义的
3.  可行性：计算机能实现的算法
4.  输入：被计算机处理的各种类型数据
5.  输出：计算机处理后输出的结果

![20190113175816312.png][]

# 算法的复杂度 #

## 时间复杂度 ##

用于衡量当问题规模不断增大，算法执行时间增长的快慢。记作T(n)，则时间复杂度主要分析T(n)的数量级。T(n)=O(f(n))，大O记法，f(n)是算法中基本运算的频度，一般考虑最坏情况下的时间复杂度

计算方法：取算法中时间增长最快的那个函数项，把它的系数改为1

## 空间复杂度 ##

用于衡量算法随着问题规模增大，算法所需空间的增长的快慢，S(n)=O(g(n))。

## 时间复杂度大小关系： ##

O(1)<O(log2n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n) 从左至右，时间性能依次降低

## 复杂度的计算 ##

### 时间复杂度： ###

复杂度是关于增长率的，所以直接忽略常数项，只关注问题规模

一般可以直接关注循环段基本操作语句的执行次数

1)单个循环体：

直接关注循环体的执行次数

2)多个循环体：

运算规则：乘法规则，加法规则

两个循环体是独立的，采用加法规则：T(n)=T1(n)+T2(n)=max(T1(n),T2(n))

两个循环体是嵌套的，采用乘法规则：T(n)=T1(n)\*T2(n)

### 空间复杂度： ###

算法运算过程中使用的辅助空间的大小

S(n)=O(f(n))

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MTEwNTM4_size_16_color_FFFFFF_t_70]: /images/20220327/dd519f9e4a25407985293709c4c88fd7.png
[20190113175816312.png]: /images/20220327/badc0f0a2bd84e2ab9d1004148d409b4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，187人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构与算法】时间复杂度和空间复杂度

我们如何判断一个算法的好坏？我们如何比较不同算法？

今天药忘吃喽~/ 2024年04月26日 02:11/ 0 赞/ 78 阅读

相关数据结构---算法的时间复杂度和空间复杂度

看到这里就结束了，我是夏目浅石，希望和你一起学习进步，刷题无数！！！希望各位大佬能一键三连支持一下博主，hhhh~我们下期见喽。

╰半橙微兮°/ 2024年04月24日 23:20/ 0 赞/ 84 阅读

相关【数据结构】算法的时间复杂度和空间复杂度

文章目录算法的时间复杂度和空间复杂度算法效率算法的复杂度时间复杂度

骑猪看日落/ 2024年04月01日 06:09/ 0 赞/ 73 阅读

相关数据结构--时间复杂度算法

数据结构–时间复杂度算法分别写出时间复杂度为o（1）、o（n）、o（n²）、o（log n）的算法： 1、O (1) include <io

青旅半醒/ 2023年07月03日 14:28/ 0 赞/ 5 阅读

相关数据结构-算法-时间复杂度计算

算法的时间复杂度定义为：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法

快来打我*/ 2022年09月17日 07:28/ 0 赞/ 199 阅读

相关数据结构与算法-时间复杂度和空间复杂度

算法复杂度分为时间复杂度和空间复杂度。其作用：时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在

雨点打透心脏的1/2处/ 2022年05月28日 01:05/ 0 赞/ 243 阅读

相关数据结构时间复杂度和空间复杂度

1、算法的概念：算法 (Algorithm)，是对特定问题求解步骤的一种描述。解决一个问题往往有不止一种方法，算法也是如此。那么解决特定问题的多个算法之间如何衡量它

喜欢ヅ旅行/ 2022年04月24日 09:32/ 0 赞/ 254 阅读

相关【数据结构和算法】3~5 时间复杂度和空间复杂度

算法效率的度量方法容易想到的方法是：把算法跑若干次，然后拿个计时器在旁边计时。这种方法被称为“事后诸葛亮”方法，也称为事后分析估算方法。事前分析估算方法：在计算机程

矫情吗；*/ 2022年04月14日 04:06/ 0 赞/ 238 阅读

相关数据结构-2算法和时间复杂度

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5

￡神魔★判官ぃ/ 2022年03月27日 12:44/ 0 赞/ 188 阅读

相关数据结构和算法_02时间复杂度和空间复杂度

[数据结构和算法\_02时间复杂度和空间复杂度][02] 高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素： 1.算法采用的策略，方案； 2.编译产生的代

喜欢ヅ旅行/ 2022年03月22日 10:58/ 0 赞/ 220 阅读