学习《代码随想录》
- 时间复杂度
- 为什么要引入时间复杂度和空间复杂度？
- 什么是时间复杂度？
- 这个O是什么意思？
- 时间复杂度越低越好？
- 内存管理
- 什么是内存空间？（C++为例）
- 为什么总说C/C++更偏向底层？
- 为什么一般不用Python写算法？
- 为什么要内存对齐？
- 内存对齐的效果？
- 空间复杂度
- 什么是空间复杂度？
时间复杂度
为什么要引入时间复杂度和空间复杂度？
从 leetcode 官方判题系统可以看出，这两个属性是评价程序性能好坏的关键指标，执行用时反映了时间复杂度，内存消耗反映空间复杂度。
什么是时间复杂度？
时间复杂度是一个函数，它定性描述了算法的运行时间，我们通常用操作单元数来代表它。记n为数据规模，f(n) 为操作单元数，O(f(n))表示时间复杂度。
这个O是什么意思？
O表示上界，也就是程序运行的最坏情况。但在业界并非如此。
例如插入排序，若输入数据有序，时间复杂度为O(n)，若逆序则为 O(n^2) ，所以它的时间复杂度为 O(n^2) ；
如快速排序，一般情况时间复杂度为O(nlogn)，但若数据有序，则为 O(n^2) ；
但是，我们仍记快速排序的时间复杂度为O(nlogn)。在业界 O 并不表示最坏，而是一般情况。
时间复杂度越低越好？
还真不是，还要考虑数据规模 n 的影响。数学中经常提到指数 2^n 的上升速度大于所有幂次，如： 100n。
这并不错，但如果我的实际业务 n 总是小于5，显然指数就更优了。
内存管理
什么是内存空间？（C++为例）
固定部分不会因为程序的运行而消耗内存，所以我们只考虑可变部分。
为什么总说C/C++更偏向底层？
因为它们内存管理机制不同。
C/C++：内存堆空间的申请和释放完全靠自己管理；
Java：依赖 JVM 实现内存管理；
Python：通过Python内存管理器管理内存，无需程序员关心。
显然C/C++灵活性更强，对底层的可操作性更强。
为什么一般不用Python写算法？
在Python中，“万物皆对象”，Python解释器将对象和数据结构封装得很好，所以它的基本数据类型所占内存要远大于纯数据类型。这很方便，但对内存有极高要求的算法来说，这种浪费是不可容忍的。
为什么要内存对齐？
- 平台原因：有些平台只能在一些地址处获取特定类型的数据。所以为了让同一个程序在多平台运行，需要内存对齐；
- 硬件原因：进行内存对齐后，CPU访问数据的速度将大大提升；
内存对齐的效果？
CPU是按照块来读取内存的，下面假设CPU将内存分为4字节的块，当前面已经有一个1字节的 char 型数据，要读取一个4字节大小的 int 型数据。
如果进行内存对齐：
不进行内存对齐：
CPU在两次寻址后，还需要将结果进行一次合并操作！
这里其实消耗了内存，但有别于 Python 的内存管理，这一点消耗我们完全可以接受，而换取来的时间复杂度性能的提升是我们更关注的。
空间复杂度
什么是空间复杂度？
一个算法在运行过程中占用内存空间大小的度量。基于它可以预先估计运行程序需要多少内存。
