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

算法的时间复杂度和空间复杂度都是用大 O 表示法,来表示的。其中 O 是个常量。
常见的 排序算法的时间复杂度:
冒泡排序、 插入排序、 希尔排序、 选择
排序的时间复杂度是 O( n^2 );
快速排序的时间复杂度是 O( n * log
n) ;
空间复杂度:
冒泡排序、 插入排序、 希尔排序、 选择
排序的空间复杂度是 O(1);
快速排序的时间复杂度是 O( log n) ;
常见的 查找算法的时间复杂度:
线性结构的查找的时间复杂度,如 二分查找(用于已经排好序
的数据,如已序的数组) ; O(n)
非线性结构的查找的时间复杂度,如 二叉查找树 ; O( log n )
排序类别 时间复杂度 空间复杂度 稳定
1 插入排序 O(n2) O(1) √
2 希尔排序 O(n2) O(1) × //Shell(希尔) 排序是基于插入排序的,
时间效率比插入、选择、冒泡高,但又比快速排序低点;
3 冒泡排序 O(n2) O(1) √
4 选择排序 O(n2) O(1) ×
5 快速排序 O(Nlogn) O(logn) ×
6 堆排序 O(Nlogn) O(1) ×
7 归并排序 O(Nlogn) O(n) √
冒泡排序、插入排序、归并排序是稳定的,算法时间复杂度是 O(n ^2) ;
选择排序、快速排序、堆排序、希尔排序都是 不稳定的;
算法的时间复杂度
一、 时间复杂度定义
定义:如果一个问题的规模是 n,解这一问题的某一算法所需要的时间为 T(n),它是 n 的某
一函数 T(n)称为这一算法的“时间复杂性” 。
当输入量 n 逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性” 。
二、大 O 表示法
我们常用大 O 表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大 O 表示只是
说有上界,由定义如果 f(n)=O(n),那显然成立 f(n)=O(n^2) ,它给你一个上界,但并不是上确
界,但人们在表示的时候一般都****惯表示前者。此外,一个问题本身也有它的复杂性, 如果
某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。
“大 O 记法 " : 在这种描述中使用的基本参数是 n,即问题实例的规模, 把复杂性或运行时间
表达为 n 的函数。这里的“ O”表示量级 (order) ,比如说“二分检索是 O(logn) 的” ,也就是说
它需要“通过 logn 量级的步骤去检索一个规模为 n 的数组”记法 O ( f(n) ) 表示当 n 增大时,
运行时间至多将以正比于 f(n) 的速度增长。
这种渐进估计对算法的理论分析和大致比较是非常有价值的, 但在实践中细节也可能造成差
异。例如,一个低附加代价的 O(n2)算法在 n 较小的情况下可能比一个高附加代价的 O(nlogn)
算法运行得更快。当然,随着 n 足够大以后,具有较慢上升函数的算法必然工作得更快。
O(1)
Temp=i;i=j;j=temp;
以上三条单个语句的频度均为 1,该程序段的执行时间是一个与问题规模 n 无关的常数。算
法的时间复杂度为常数阶,记作 T(n)=O(1)。如果算法的执行时间不随着问题规模 n 的增加
而增长, 即使算法中有上千条