刷题
刷题
learn
learn
日期
Aug 28, 2024
- 常数操作，固定时间的操作，执行时间和数据量无关
- 时间复杂度，一个和数据量有关、只要高阶项、不要低阶项、不要常数项的操作次数表达式
- 严格固定流程的算法，一定要强调最差情况，比如插入排序
- 算法流程上利用随机行为作为重要部分的，要看平均或者期望的时间复杂度，因为最差的时间复杂度无意义 用生成相邻值不同的数组来说明
- 算法流程上利用随机行为作为重要部分的，还有随机快速排序、跳表 也只在乎平均或者期望的时间复杂度，因为最差的时间复杂度无意义
- 时间复杂度的内涵：描述算法运行时间和数据量大小的关系，而且当数据量很大时，这种关系相当的本质，并且排除了常数时间的干扰
- 空间复杂度，强调额外空间；常数项时间，放弃理论分析、选择用实验来确定，因为不同常数操作的时间不同
- 什么叫最优解，先满足时间复杂度最优，然后尽量少用空间的解。
- 时间复杂度的均摊，用动态数组的扩容来说明（等比数列、均摊的意义） 并查集、单调队列、单调栈、哈希表等结构，均有这个概念
- 不要用代码结构来判断时间复杂度，比如只有一个
while循环的冒泡排序，其实时间复杂度可能是
- 不要用代码结构来判断时间复杂度，比如：，是调和级数，虽然不收敛无法直接求和，但是可以通过上下界时间复杂度都是说明其时间复杂度也是
- 时间复杂度只能是对算法流程充分理解才能分析出来，而不是简单看代码结构！这是一个常见的错误 甚至有些算法的实现使用了多层循环嵌套，但实际上时间复杂度也是
- 常见复杂度一览：，，，，，…，，，…，，…，
- 时间复杂度非常重要，可以直接判断某个方法能不能通过一个题目，根据题量猜解法