时间复杂度分析

1. 只关注循环执行次数最多的一段代码
2. 总复杂度等于量级最大的那段代码的复杂度
3. 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

我们把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。非多项式量级只有两个：O(2n) 和 O(n!).当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

常见时间复杂度实例分析

• O(1)

  一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

• O(logn)、O(nlogn)

  我们知道，对数之间是可以互相转换的，log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

• O(m+n)、O(m*n)

最好、最坏情况时间复杂度和平均情况时间复杂度

只有同一块代码在不同的情况下，时间复杂度有量级的差距，才使用这三种时间复杂度区分

数组

• 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

• 是连续的内存空间和相同类型的数据使得数组支持随机随机访问，查找高效，增删低效

• 插入数据时间复杂度分析

  • 插入位置为尾部 =>O(1)
  • 插入位置为开头 =>O(n)

• 删除

  为了避免 d，e，f，g，h 这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

  如果你了解 JVM，你会发现，这不就是 JVM 标记清除垃圾回收算法的核心思想吗？没错，数据结构和算法的魅力就在于此，很多时候我们并不是要去死记硬背某个数据结构或者算法，而是要学习它背后的思想和处理技巧，这些东西才是最有价值的。如果你细心留意，不管是在软件开发还是架构设计中，总能找到某些算法和数据结构的影子。

容器与数组的选取

容器优势：

• 封装数组操作细节
• 动态扩容（如ArrayList自动扩容1.5倍）

扩容涉及到内存申请和数据搬移，最好事先指定数据大小

数组优势的场景：

• ArrayList无法存储基本类型，需要自动装箱成Integer、Long，有性能消耗，需要极致性能的场景时候可以用数组
• 数据大小已知，对数据操作十分简单，用不到ArrayList大部分方法
• 多维数组的情况下数组更加直观

总结

对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

• 数组从0计数的原因：

  a[k]_address = base_address + k * type_size
  

链表

• 易于增删，难于随机访问，访问复杂度为O(n)

• 循环链表用于环形结构的数据

• 删除一个数据有两种情况：

  • 删除给定指针的节点（寻找的过程为O(n)）
  • 删除结点中值等于某个值的结点 (单链表需要寻找前驱结点，仍旧是O(n),双向链表不需要寻找)

• 如果是有序双向链表，可以根据上次查找位置，根据大小关系，往前或者往后查找

• 在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛，LinkHashMap用的就是双向列表的结构

  用空间换时间的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。

• ArrayList 容器本质是数组而不是链表，动态扩容是通过申请内存+拷贝数据实现的

• 对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。

链表代码技巧

• 理解指针或引用的含义

  将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

• 警惕指针丢失和内存泄漏

  • 插入结点时，一定是先把结点接入再断开链表，而不是先断开链表再接入，否则会找不到后续结点
  • 删除的时候也要记录一下删除的结点，删除以后释放内存

• 利用哨兵简化实现难度

  • 利用将最后一位替换为要寻找数值的方式，保证find函数一定存在要找的数字，并且它就是边界，减少对比的时间消耗

• 重点留意边界条件处理（常用边界检查）

  • 如果链表为空时，代码是否能正常工作？

  • 如果链表只包含一个结点时，代码是否能正常工作？

  • 如果链表只包含两个结点时，代码是否能正常工作？

  • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

    其实就是0，1，2外加头尾

• 举例画图，辅助思考

• 常用处理总结

  1. 保存下一个
  2. 断链并接上新next
  3. 赋值新头部