算法(四)-算法复杂度

关于算法的一些基础知识点

通俗来讲，算法是解决问题的有限步骤。

算法的特性：
输入输出：一定有输出，不一定有输入。
有穷性：执行步数有限，执行时间可控。
可行性：可以被计算机执行。
确定性：同样的输入，有同样的输出。

算法特性

好算法满足的要求：
正确性：保证算法可以得出正确的结果。
（1）无语法错误
（2）合法的输入，可以得到正确的输出
（3）非法的输入，也可以得到符合规则的输出
（4）对于刁难的输入，也可以得到正确的输出
可读性：易于阅读，理解和交流。
健壮性：指容错能力
时间效率高和储存量低：响应快，不好存储，用最少的钱，创造最大的价值。

算法要求

算法的效率评估：
1.事后统计法：通过输入大量数据，在计算机上运行程序，计算运行时间来判断效率高低。（消耗非常多的人力，物力，并且容易受程序所运行的环境影响，不推荐）
2.事前估算法：通过统计学来计算算法的效率高低。（输入规模和算法本身）

算法复杂度计算（O(n)）：
推导：
1.将常数项全部用1替代。
2.只保留最高阶项。
3.把与最高阶项相乘的常数去掉，如果最高阶是常数则以1替代。

常见的时间复杂度.png

最坏时间复杂度：运行时间将不会再坏了，一般运行时间都算最坏的时间复杂度。
平均时间复杂度：通过数据估算得到的平均时间复杂度。

空间复杂度：算法计算过程所需要用到的空间大小。

以上，就是关于算法的一些基础知识点