算法+数据结构=程序,今天就来说说递归+排序+查找,再加上树与图

　　

著名数据专家沃斯曾说:算法+数据结构=程序

　　

上次讲了数据结构

　　

这回就讲讲算法

　　复杂度 　　

复杂度分析,是贯彻数据结构和算法中的一项基础技能,学习数据结构和算法的目的,无非就是要写出占用空间更小,运行时间更短的代码。

　　时间复杂度 　　

　　<李>大O表示法: 　　<代码> T (n)=O (f (n))

　　

　　<李>表示代码执行时间随数据规模增长的 　　(注意只是表示“变化趋势”) 　　<李>由于只是表示变化趋势,一般计算复杂度时,会忽略低阶,常量,系数

　　

　　<李> 　　 　　几种常见的时间复杂度量级: 　　 　　 　　
　　李image.png

　　

多项式量级:

　　

　　<李>常数阶O(1) 　　<李>对数阶O (logn) 　　<李>线性阶O (n) 　　<李>线性对数阶O (nlogn) 　　<李>平方阶O (n2) O (n3)…李O (n ^ k)

　　

非多项式量级:(n越多,执行时间急剧上升,性能低)

　　

　　<李>指数阶O (2 ^ n) 　　<李>阶乘阶O (n)

　　

　　<李>加法法则和乘法法则李

　　

　　<李>加法法则:总复杂度等于量级最大的那段代码的复杂度 　　<李>乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积李

　　

　　<李>平均时间复杂度:

　　

　　<李>也叫加权平均时间复杂度或者期望时间复杂度。 　　<李>要会计算:最好,最坏,平均时间李

　　

　　<李>均摊时间复杂度

　　

　　<李>特殊的平均时间复杂度 　　<李>相当于算法有规律可循,计算时间时,可以把一次耗时多的操纵的时间,均摊给多次耗时少的操纵。

　　算法 　　 1。递归 　　

可以用递归的条件:

　　

　　<李>一个问题的解可以分解为几个子问题的解 　　<李>这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样李 　　<李>存在递归终止条件

　　

写递归算法的思路:

　　

　　<李>归纳出递归表达式李 　　<李>寻找终止条件

　　

递归代码的弊端:

　　

　　<李>堆栈溢出李 　　<李>可能会重复计算李 　　<李>函数调用耗时多 　　<李>空间复杂度高李

　　 2。排序 　　

　　

　　

　　<李>执行效率

　　

　　<李>最好时间复杂度 　　<李>最坏时间复杂度 　　<李>平均时间复杂度 　　<李>时间复杂度的系数,常数,低阶(因为排序的数据规模一般不会非常大) 　　<李>比较,交换的次数

　　

　　<李>额外内存消耗(内存消耗为O(1)的称为原地排序) 　　<李>稳定性,是否是稳定排序(即如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变)

　　

　　

　　

　　<李> O (n2):冒泡排序,插入排序,选择排序李 　　<李> O (nlogn):归并排序,快速排序李 　　<李> O (n):桶排序,计数排的序,基数排序(条件苛刻,适用于部分场景)

　　

2.1冒泡排序

　　

原理:从下往上,逐次比较两个相邻的数据,如果下面的数据比上面的数据大,则把这两个数据的位置互换。

　　 　　 　　
　　image.png 　　 　　 　　
　　image.png 　　

　　<李>最好时间复杂度O (n) 　　<李>最坏时间复杂度O (n ^ 2) 　　<李>平均时间复杂度O (n ^ 2) 　　<李>原地排序,稳定排序李

　　

2.2插入排序

　　

原理:分为已排区域和未排区域,每次拿未排区域中的第一个数,插入到已排区域中正确的位置。

　　 　　

算法+数据结构=程序,今天就来说说递归+排序+查找,再加上树与图