在生活中你的最常用的算法是怎么运作的_python

资料来源：网络整理时间：2023/3/9 4:14:56 共计：3566 浏览

在生活中你的最常用的算法是怎么运作的？

概念

算法（Algorithm）是基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。不正式地说，算法是任何定义明确的计算过程，该过程取某个值或值的集合作为输入，并产生某个值或值的集合作为输出，算法就是这样的把输入转换成输出的计算步骤的一个序列。[1]

必备特征

算法必须具有以下特征：

输入：待计算问题的任一实例，都需要以某种方式交给对应的算法，对所求解问题特定实例的这种描述统称为输入；

输出：经计算和处理之后得到的信息，即针对输入问题实例的答案，称作输出；

确定性：算法应可描述为由若干语义明确的基本操作组成的指令序列；

可行性：每一基本操作在对应的计算模型中均可兑现；

有穷性：任意算法都应在执行有限次基本操作之后终止并给出输出。

实际例子

算法不是计算机领域中才有的概念，不仅仅局限于编程语言，它可以用任何方式来描述，比如对于问题：过直线l上给定的点P，作该直线的垂线。古埃及人解决该问题的一个算法为：

输入：直线l及其上一点P

输出：经过P且垂直于l的直线

1. 取12段等长绳索，依次首尾联结成环，联结处称作“结”，按顺时针方向编号为0到11

2. 奴隶A看管0号结，将其固定于点P处

3. 奴隶B牵动4号结，将绳索沿直线l方向尽可能地拉直

4. 奴隶C牵动9号结，将绳索尽可能地拉直

5. 经过0号和9号结，绘制一条直线

计算机中的算法则是描述计算机上的计算过程，比如插入排序算法的伪代码描述：

输入：n个数的一个序列<a[1], a[2], ..., a[n]>

输出：输入序列的一个排列<b[1], b[2], ..., b[n]>，满足b[1] <= b[2] <= ... <= b[n]

INSERTION-SORT(A)

for j = 2 to A.length

key = A[j]

i = j - 1

while i > 0 and A[i] > key

A[i + 1] = A[i]

i = i - 1

A[i + 1] = key

上述算法可以用不同的编程语言来描述，比如用Python描述：

def insertSort(A):

for j in range(2, len(A)):

key = A[j]

i = j - 1

while i > 0 and A[i] > key:

A[i + 1] = A[i]

i = i - 1

A[i + 1] = key

比如用C++描述：

template<typename T>

void insertSort(std::vector<T>& A)

{

for (int j = 2; j < A.size(); ++j)

{

auto key = A[j];

int i = j - 1;

while (i > 0 && A[i] > key)

{

A[i + 1] = A[i];

--i;

A[i + 1] = key;

}

优劣分析

由于计算机不是无限快，内存不是免费的，计算时间和空间是一种有限资源，高效的算法可以更好地利用这些资源，因此算法可以像计算机硬件一样视为一种技术。度量算法成本的方式称为复杂度分析，复杂度可分为时间复杂度和空间复杂度。由于运行任一算法的空间消耗都不会多于运行期间进行的基本操作次数，即时间复杂度本身就是空间复杂度的上界，因此复杂度分析主要关注时间复杂度，而时间复杂度分析主要关注最坏情况下的运行时间，即最长运行时间。复杂度分析一般用渐进记号大O表示，它用一个函数来描述某个函数的数量级上界。最低复杂度是O(1)，代表常数时间复杂度，因为不能指望没有任何代价来运行算法。依次递增的常见复杂度层级还有O(log n)、 O(√n)、O(n)、O(nlog n)、O(n^2)、O(n^3）、O(2^n)等。

常见种类

计算机中存储和组织数据的方式称为数据结构，因此计算机中的算法通常也与数据结构紧密相连，最常见的一类算法就是数据结构的插入、删除、查找、遍历、排序等，一般此类算法会封装为编程语言的标准之一，如C++ STL中的算法。除了数据结构相关算法外，还有图算法、数论算法、矩阵运算、计算几何、压缩算法、加密算法、数据挖掘算法、并行算法等。算法设计与分析的基本方法有蛮力法、分治法、动态规划、贪心算法等。并非所有问题都存在有效算法，对于NP完全问题是否存在有效算法是未知的。[2]

版权说明：
本网站凡注明“广州京杭原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。

·上一条：100能被2整除的数_python | ·下一条：计算机中前台和后台是什么意思_java