算法讲解007【入门】时间复杂度和空间复杂度

时间复杂度和空间复杂度 大纲

1. 常数操作，固定时间的操作，执行时间和数据量无关

2. 时间复杂度，一个和数据量有关、只要高阶项、不要低阶项、不要常数项的操作次数表达式
1. 举例：选择、冒泡（O(n²)）、插入

3. 严格固定流程的算法，一定强调最差情况！比如插入排序

4. 算法流程上利用随机行为作为重要部分的，要看平均或者期望的时间复杂度，因为最差的时间复杂度无意义
1. 用生成相邻值不同的数组来说明

5. 算法流程上利用随机行为作为重要部分的，还有随机快速排序（【必备】课）、跳表（【扩展】课）
1. 也只在乎平均或者期望的时间复杂度，因为最差的时间复杂度无意义

6. 时间复杂度的内涵：描述算法运行时间和数据量大小的关系，而且当数据量很大很大时，这种关系相当的本质，并且排除了低阶项、常数时间的干扰

7. 空间复杂度，强调额外空间；常数项时间，放弃理论分析、选择用实验来确定，因为不同常数操作的时间不同

8. 什么叫最优解，先满足时间复杂度最优，然后尽量少用空间的解

9. 时间复杂度的均摊，用动态数组的扩容来说明（等比数列、均摊的意义）
1. 并查集、单调队列、单调栈、哈希表等结构，均有这个概念。这些内容【必备】课都会讲

10. 不要用代码结构来判断时间复杂度，比如只有一个while循环的冒泡排序，其实时间复杂度O(N^2)

11. 不要用代码结构来判断时间复杂度，比如：N/1 + N/2 + N/3 + … + N/N，这个流程的时间复杂度是O(N * logN)，著名的调和级数

12. 时间复杂度只能是对算法流程充分理解才能分析出来，而不是简单的看代码结构！这是一个常见的错误！

1. 常见复杂度一览：

1. 时间复杂度非常重要，可以直接判断某个方法能不能通过一个题目，根据数据量猜解法，【必备】课都会讲

2. 整套课会讲很多算法和数据结构，也会见到很多的时间复杂度的表达，持续看课即可

视频笔记

1. 常数操作，固定时间的操作，执行时间和数据量无关
1. 固定操作量，和数据大小无关
2. 寻址、位运算、哈希等等，即使常数操作也是有快慢的

2. 时间复杂度，一个和数据量有关、只要高阶项、不要低阶项、不要常数项的操作次数表达式
1. 只看最高阶项
2. 举例：选择、冒泡（O(n²)）、插入

3. 严格固定流程的算法，一定强调最差情况！比如插入排序
1. 只要算法中没有随机的成分，那就是固定流程
2. 我们拿最差情况这个算法都做得不太糟来判断它的 时间复杂度 很合理

4. 算法流程上利用随机行为作为重要部分的，要看平均或者期望的时间复杂度，因为最差的时间复杂度无意义
1. 用生成相邻值不同的数组来说明
1. 有可能直接全部都是 33333......的数组，这就会导致它会一直重复下去，正无穷

5. 算法流程上利用随机行为作为重要部分的，还有随机快速排序（【必备】课）、跳表（【扩展】课）
1. 也只在乎平均或者期望的时间复杂度，因为最差的时间复杂度无意义

6. 时间复杂度的内涵：描述算法运行时间和数据量大小的关系，而且当数据量很大很大时，这种关系相当的本质，并且排除了低阶项、常数时间的干扰

7. 空间复杂度，强调额外空间；常数项时间，放弃理论分析、选择用实验来确定，因为不同常数操作的时间不同
1. 为了完成这个算法的整套流程不得不开辟的空间大小，和入参、出参无关

8. 什么叫最优解，先满足时间复杂度最优，然后尽量少用空间的解

9. 时间复杂度的均摊，用动态数组的扩容来说明（等比数列、均摊的意义）
1. 并查集、单调队列、单调栈、哈希表等结构，均有这个概念。这些内容【必备】课都会讲
2. 只看规模，不要关注常数
3. 使用动态数组，每次插入数据，然后扩容，再插入，再扩容
4. 时间复杂度始终 < 2*n，那么最终每个数据插入均摊就是 O(1)

10. 不要用代码结构来判断时间复杂度，比如只有一个while循环的冒泡排序，其实时间复杂度O(N^2)
1. // 只用一个循环完成冒泡排序 // 但这是时间复杂度O(N^2)的！ public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int n = arr.length; int end = n - 1, i = 0; while (end > 0) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } if (i < end - 1) { i++; } else { end--; i = 0; } } }​

11. 不要用代码结构来判断时间复杂度，比如：N/1 + N/2 + N/3 + … + N/N，这个流程的时间复杂度是O(N * logN)，著名的调和级数

12. int N = 200000; long start; long end; System.out.println("测试开始"); start = System.currentTimeMillis(); for (int i = 1; i <= N; i++) { for (int j = i; j <= N; j += i) { // 这两个嵌套for循环的流程，时间复杂度为O(N * logN) // 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + ... + 1/n，也叫"调和级数"，收敛于O(logN) // 所以如果一个流程的表达式 : n/1 + n/2 + n/3 + ... + n/n // 那么这个流程时间复杂度O(N * logN) } }

14. 时间复杂度只能是对算法流程充分理解才能分析出来，而不是简单的看代码结构！这是一个常见的错误！

1. 常见复杂度一览：

1. 时间复杂度非常重要，可以直接判断某个方法能不能通过一个题目，根据数据量猜解法，【必备】课都会讲

2. 整套课会讲很多算法和数据结构，也会见到很多的时间复杂度的表达，持续看课即可

算法讲解008【入门】算法和数据结构简介

说一个我觉得比较有趣、有用的算法分类

1. 硬计算类算法、软计算类算法 注意：这两个名词都不是计算机科学或算法中的标准术语

2. 那为啥要提这个呢？因为很有现实意义。

3. 硬计算类算法：精确求解。但是某些问题使用硬计算类的算法，可能会让计算的复杂度较高 大厂算法和数据结构笔试、面试题、acm比赛或者和acm形式类似的比赛，考察的都是硬计算类算法。

4. 软计算类算法：更注重逼近解决问题，而不是精确求解。计算时间可控 比如：模糊逻辑、神经网络、进化计算、概率理论、混沌理论、支持向量机、群体智能

5. 硬计算类算法是所有程序员岗位都会考、任何写代码的工作都会用到的。前端、后端、架构、算法所有岗位都要用到。 但是算法工程师除了掌握硬计算类的算法之外，还需要掌握软计算类的算法。

6. 说一个我觉得比较宏观的数据结构分类
连续结构（内存地址连续）
跳转结构（内存地址不连续）

• 任何数据结构都一定是这两个结构拼出来的！没有例外！

• 数据结构太多了，从链表、队列、栈，到可持久化线段树、树链剖分、后缀数组等等结构

• 后面的课都会讲到！