算法基础一：算法设计与分析
一、什么是算法
- 算法是程序的灵魂
- 是解决一个计算问题的一系列计算步骤的 有序的 合理的排列。
本次算法的基础学习过程将从
渐增型算法
分治算法
动态规划
贪婪策略
回溯算法
来学习。
二、算法分析的基础概念
一般来说，解决同一问题的算法，需要的资源越少，我们认为越优秀。计算算法运行时所需资源的量的过程称为算法复杂性分析，简称为算法分析。理论上，算法分析既要计算算法的时间复杂性，又要计算它的空间复杂性。然而，算法的运行时间都是消耗在数据处理上面的，人们更多关注的时算法的时间复杂性分析。
时间复杂性：假设有一台抽象的计算机，它只用一个处理机，却有无限量的随机存储器。它的有限个基本操作——算术运算、逻辑运算和数据的移动均在有限固定的时间内完成，我们进一步假定这些基本操作都消耗一个时间单位。称此计算机为随机访问计算机，简记为RAM。算法在RAM上运行所需要的时间，显然就是执行基本操作的次数。
一般来说：规模越大，需要执行的基本操作也就越多，运行时间就越长。此外，即使问题输入的规模一定，不同的输入，也会导致运行时间的不同。有以下三种情况：
- 对于固定的输入规模，使得运算时间最长的输入所消耗的运行时间称为算法的最坏情形时间。
- 对于固定的输入规模，使得运算时间最短的输入所消耗的时间，称为最好情形时间。
- 假定固定的输入规模为n，所有不同输入构成的集合为Dn，对问题的每一个输入为I∈Dn，若已知该输入发生的概率为P(I)，对应的运行时间T(I)，运行时间的数学期望值
算法基础一：算法设计与分析
算法最坏情形时间可以视为算法对固定输入规模n的运行时间的上界，用它来表示算法的时间复杂性是合理的。我们把算法的运行时间记为T，输入的规模记为n。则根据以上说明可以知道，T是n的递增函数，我们用T(n)来表示算法的运行时间。
三、算法的渐进运行时间
由于计算机技术发展迅猛，所以要解决的问题输入规模也就越来越大，所以对固定的n来计算T(n)的意义并不大，我们更倾向于当
T(n)趋于无穷大的快慢来分析算法的时间复杂性。我们往往用几个函数Y(n)：