算法基础

算法基础

算法基础知识

算法的五个重要特性：

• 有穷性
• 确定性
• 可行性
• 输入：0或多个
• 输出：一个或多个

算法分析基础

算法复杂性包括两个方面，一个是算法效率的度量（时间复杂度），一个是算法运行所需要的计算机资源量的度量（空间复杂度），这也是评价算法优劣的重要依据。

时间复杂度

一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模n的某个函数T（n）。由于许多情况下要精确计算T（n）是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。

我们通常使用"O（）"来表示时间复杂度，其定义如下：如果存在两个正常数c和m，对于所有的n，当n≥m时有f（n）≤cg（n），则有f（n）=O（g（n））也就是说，随着n的增大，f（n）渐进地不大于g（n）。例如，一个程序的实际执行时间为3n^3+2n^2+n,则T（n）=O（n^3）。T（n）和n^3的值随n的增长渐近地靠拢。常见的渐进时间复杂度有：

空间复杂度

一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。它通常包括固定部分和可变部分两个部分。

在算法的分析与设计中，经常会发现时间复杂度和空间复杂度之间有着微妙的关系，经常可以相互转换，也就是可以利用空间来换时间，也可以用时间来换空间。

常用算法

参考资料

视频

希赛网

文字版

https://cloud.tencent.com/developer/article/2385825

https://cloud.tencent.com/developer/article/2387285

https://blog.csdn.net/chengsw1993/article/details/125714839