学习极客大学覃算法相关课程记录
常见的几种时间复杂度
- O(1)：常量阶，运行时间为常量 Constant Complexity
- O(logn)：对数阶，如二分搜索算法 Logarithmic Complexity
- O(nlogn)：对数阶，如快速排序算法 Logarithmic Complexity
- O(n)：线性阶，如n个数内找最大值 Linear Complexity
- O(n^2)：平方阶，如选择排序，冒泡排序 N Square Complexity
- O(n^3)：立方阶，如两个n阶矩阵的乘法运算 N cubic Complexity
- O(2^n)：指数阶，如n个元素集合的所有子集的算法 Exponential Growth
- O(n!)：阶乘阶，如n个元素全部排列的算法 Factorial
开发流程四件套
- 确认需求
- 实现问题的几种办法
- 挑选时间和空间复杂度较低的并且占用资源较少的方法
- 着手开发，测试
主定理
常见的几种时间复杂度题目
空间复杂度
- 数组的长度（a[n] 空间复杂度就是n，a[n][n] 空间复杂度就是n平方）
- 递归的深度
斐波那契数列-爬楼梯问题
不同实现方式对应的时间和空间复杂度
-
正常写法
-
方法二：记忆化递归
-
方法三：动态规划算法
-
方法四：斐波那契数（对方法三内存上优化）
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/tech/aiops/1419.html