算法的时间复杂度和空间复杂度

一、算法

1.算法的五大特性：有穷性、确定性、可行性、输入、输出

2.评价算法优劣的基本标准：正确性、可读性、健壮性、高效性

算法的好坏主要由时间复杂度和空间复杂度来评判。

二、时间复杂度

1.作用：评估执行程序所需的时间，可以估算出程序对处理器的使用程度。

2.时间频度：

 3.时间复杂度的定义：

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数f（n），使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数，记作T（n）=O（f（n）），我们也称O（f（n））为算法的渐进时间复杂度，简称时间复杂度。

4.时间复杂度的计算步骤：

 

5.常见的时间复杂度：

常见的时间复杂度按数量级递增排列依次为：常量阶O(1)、对数阶O(log)、线性阶O(n)、线性对数阶O(n*log)、平方阶O()、立方阶O()、.......k次方阶O()、指数阶O()

 

 6.最好、最坏和平均时间复杂度：

三、空间复杂度

1.作用：评估执行程序所需的存储空间，可以估算出程序对计算机内存的使用程度。