算法基本概念

5个特性：

  1）有穷性

  2）确定性

  3）可行性

  4）输入

  5）输出

评价算法的优劣：

  1）时间复杂度

  它定性描述算法的运行时间。一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。

  时间复杂度又分为：最坏时间复杂度，平均时间复杂度，最好时间复杂度。

    最坏时间复杂度是指最坏情况下，算法的时间复杂度。

    平均时间复杂度是指所有输入实力在等概率出现的情况下，算法的期望运行时间。

    最好时间复杂度是指最好情况下，算法的时间复杂度。

  算法时间复杂度应该不难求解吧。

如果循环主体中的变量参与循环条件的判断，这时候计算循环体里面的操作次数，得出时间复杂度。

如果循环主体中的变量与循环条件无关，就采用数学归纳法或间接累计循环次数。

可能觉得有点模糊，不如做两道题，自然茅舍顿开。

  常见的渐进时间复杂度为：

$$O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$$

  2）空间复杂度

  空间复杂度S(n) 就是该算法所耗费的存储空间，是一个问题规模n的函数。这里有一点要注意，就是算法原地工作是指算法所需的辅助空间为常量，即O(1)。