“算法特性和复杂度”的版本间的差异

来自姬鸿昌的知识库
跳到导航 跳到搜索
 
（未显示同一用户的3个中间版本）
第41行： 第41行：
  
 
也就是说，随着n的增大，f(n)渐进地不大于g(n)。
 
也就是说，随着n的增大，f(n)渐进地不大于g(n)。
 +
 +
  
 
例如，一个程序的实际执行时间为T=(n)=3n<sup>3</sup>+2n<sup>2</sup>+n，则T(n)=O(n<sup>3</sup>)。
 
例如，一个程序的实际执行时间为T=(n)=3n<sup>3</sup>+2n<sup>2</sup>+n，则T(n)=O(n<sup>3</sup>)。
第49行： 第51行：
  
 
O(1) < O(log<sub>2</sub>n) < O(n) < O(nlog<sub>2</sub>n) < O(n<sup>2</sup>) < O(n<sup>3</sup>) < O(2<sup>n</sup>)
 
O(1) < O(log<sub>2</sub>n) < O(n) < O(nlog<sub>2</sub>n) < O(n<sup>2</sup>) < O(n<sup>3</sup>) < O(2<sup>n</sup>)
 +
 +
 +
  
 
==== 空间复杂度 ====
 
==== 空间复杂度 ====
第54行： 第59行：
  
 
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。
 
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。
 +
 +
 +
 +
=== 考点：算法特性考察 ===
 +
一个计算机算法是对特定问题求解步骤的一种描述。
 +
 +
算法的（）是指算法能够对不合理数据及非法操作进行识别和处理的能力。
 +
 +
A、有穷性
 +
 +
B、可行性
 +
 +
C、确定性
 +
 +
D、健壮性  √

2022年9月21日 (三) 02:33的最新版本

https://www.bilibili.com/video/BV1hg411V7Bm?p=64

算法的基本特性

有穷性：执行有穷步之后结束。

确定性：算法中每一条指令都必须有确定的含义，不能含糊不清。

输入输出数目约定：输入（≥0）。输出（≥1）。

有效性（可行性）：算法的每个步骤都有效执行并能得到确定的结果。

例如：a=0，b/a就是无效的。


算法评价指标

正确性：正确实现算法功能，最重要的指标

友好性：具有良好的使用性

可读性：可读的、可以理解的，方便分析、修改和移植

健壮性：对不合理的数据或非法的操作能进行检查、纠正

效率：对计算机资源的消耗，包括计算机内存和运行时间的消耗


时间复杂度和空间复杂度

时间复杂度

程序运行从开始到结束所需要的时间。

通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。

一般来说，算法中原操作重复执行的次数是规模n的某个函数T(n)。

由于许多情况下要精确计算T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。

其定义如下：

如果存在两个常数c和m，对于所有的n，当n≥m时有f(n)≤cg(n)，则有f(n)=O(g(n))。

也就是说，随着n的增大，f(n)渐进地不大于g(n)。


例如，一个程序的实际执行时间为T=(n)=3n3+2n2+n，则T(n)=O(n3)。


常见的对算法执行所需时间的度量：

O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n)



空间复杂度

是指对一个算法在运行过程中临时占用存储空间大小的度量。

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。


考点：算法特性考察

一个计算机算法是对特定问题求解步骤的一种描述。

算法的（）是指算法能够对不合理数据及非法操作进行识别和处理的能力。

A、有穷性

B、可行性

C、确定性

D、健壮性 √

取自“https://www.jihongchang.top/index.php?title=算法特性和复杂度&oldid=2170”