[TOC] ## 算法的概念 基本概念 个问题可以有多种算法,每种算法都不同的效率一个算法具有五个特征:有穷性、确切性、输入项、输出项、可行性 ## 时间复杂度和空间复杂度的概念 算法评定 算法分析的目的在于选择合适算法和改进算法一个算法的评价主要从时间复杂度和空间复杂度来考虑 ### 时间复杂度 执行算法所需要的计算工作量。一般来说,计算机算法是问题规模n的函数f(n),算法的时间复杂度也因此记做`T(n)=O(f(n))` 问题的规模n越大,算法执行的时间的增长率与f(n)的增长率正相关,称作渐进时间复杂度( Asymptotic Time Complexity) #### 时间复杂度计算方式 o(n^2)、O(1)、O(n)? 如果 n 的数未知 那么复杂度就是`O(n)`, 如果 n 个数,但是支取前三个,则不用`O(3)`,而是用`O(1)`,括号里为常数则多为1  - 得出算法的计算次数公式 - 用常数1来取代所有时间中的所有加法常数 - 在修改后的运行次数函数中,只保留最高阶项 如`O(n^2+n+1)`则只要 `O(n^2)` - 如果最高阶存在且不是1,则去除与这个项相乘的常数 #### 举例 常数阶:`O(1)` 线性阶:`O(n)` 平(立)方阶:`O(n^2)`或`o(n^3)` ``` 由于是循环了n 的平方 所以其复杂度 为 O(n^2) for($i=1;$i<=$n;$i++){ for($j=1;$j<=$n;$j++){ $sum +=$ } } ``` 特殊平方阶:`o(n^2/2+n/2)->o(nA2)` ``` // 其复杂度 为 `O(n^2+n+1) -> O(n^2) for(){ for(){} } for(){} echo $n ``` 对数阶`O(log(2n))`; ``` while($n >=1)( $n=$n/2 } n(2^m)=1 -> 2^m=2 -> m=log(2n) -> O(log(2n)) ``` 常见时间复杂度:常数阶、线性阶、平方阶、立方阶、对数阶、 nlog2n阶、指数阶 `O(1)>O(log2n)>O(n)>O(nlog2n)>O(n^2)>(n^3)>O(2^n)>O(n!)>O(n^n)` #### 空间复杂度 算法需要消耗的内存空间,记作`S(n)=O(f(n))` 包括程序代码所占用的空间,输入数据所占用的空间和辅助变量所占用的空间这三个方面 计算和表示方法与时间复杂度类似,一般用复杂度的渐近性来表示 有时用空间换取时间 冒泡排序的元素交换,空间复杂度O(1),因为要加的数永远只有一个 ### 排序算法 #### 冒泡排序 原理:两两相邻的数进行比较,如果反序就交换,否则不交换时间复杂度:最坏`(O(n^2),平均(O(n^2)` 如: 对,1,2,3,4,5,6进行 排序 #### 直接插入排序 原理 每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序 时间复杂度:最坏(O(n^2),平均(O(n^2) 空间复杂度:O(1) #### 希尔排序 原理 把待排序的数据根据增量分成几个子序列,对子序列进行插入排序,直到增量为1,直接进行插入排序;增量的排序,一般是数组的长度的一半,再变为原来增量的一半,直到增量为1 时间复杂度:最差(O(n^2)),平均(O(n(log2n) 空间复杂度:O(1) #### 选择排序 原理 每次从待排序的数据元素中选岀最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 时间复杂度:最坏(O(n^2),平均(O(n^2) 空间复杂度:O(1) #### 快速排序 原理 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按照此方法对这两部分数据分别进行快速排序,整个排序过程可以递归完 成 时间复杂度:最差(O(n^2),平均(O(n(log2n) 空间复杂度:最差(O(n),平均(O(log2n) #### 堆排序 原理 把待排序的元素按照大小在二叉树位置上排列,排序好的元素要满足:父节点的元素要大于等于子节点;这个过程叫做堆化过程,如果根节点存放的是最大的数,则叫做大根堆,如果是最小,就叫小根堆,可以把根节点拿出来,然后再堆化,循环到最后一个节点 时间复杂度:最差(O(n(log2n),平均(O(nl(og2n) 空间复杂度:O(1) #### 归并排序 原理 将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个有序的子序列,再把有序的子序列合并为整体有序序列 时间复杂度:最差O(n(log2n),平均(O(n(log2n) 空间复杂度:O(n) ## 查找算法 ### 二分查找 原理:从数组的中间元素开始,如果中间元素正好是要查找的元素,搜索结束,如果某一个特定元素大于或者小于中间元素,则在数组大于或者小于中间元素的那一半中查找,而且跟开始一样从中间开始比较,如果某一步骤数组为空,代表找不到。 时间复杂度:最差(O(log2n),平均(O(log2n) 空间复杂度:迭代(O(1))、递归(O(log2n)) ### 顺序查找 原理:按一定的顺序检查数组中每一个元素,直到找到所要寻找的特定值为止。 时间复杂度:最差(O(n),平均(O(n)) 空间复杂度:O(1)