数据结构和算法 总结和应用笔记

知识点导图 图片地址

大O复杂度表示法 教程地址

测试环境的硬件和数据规模会影响算法的测试结果

因此需要不用具体的测试数据测试,粗略的估计算法执行效率的方法(复杂度表示法)

分为时间复杂度空间复杂度

时间复杂度
T(n) = O(f(n))
#渐进时间复杂度(时间复杂度)公式说明
T(n)所有代码的执行时间,n表示数据规模大小(循环处理次数),f(n)每行代码执行次数总和,f(n)是运算形式的表达式(例:(2n+2)),O表示代码执行时间T(n)和f(n)表达式成正比
公式表示代码执行时间随数据规模增长的变化趋势

时间复杂度分析方法

1.只关注循环次数最多的一段代码

2.加法法则:总复杂度等于量级最大的那段代码的复杂度

3.乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积