一、算法的基本特征

一个算法应具备以下五个基本特征：

1. 有穷性：算法必须在 有限步骤 内结束。
2. 确定性：每一步操作都有明确含义。
3. 可行性：每一步操作可在有限时间内完成。
4. 有输入：算法有零个或多个输入。
5. 有输出：算法至少产生一个输出。

示例：

while(true) { 0; } // 无穷循环，不满足有穷性

---

二、算法设计原则

在设计和实现算法时，应遵循以下原则：

1. 正确性：算法结果必须正确。算法再好结果不正确都是乱搞。
2. 可读性：代码易于理解和维护。便于团队写作。
3. 健壮性：系统稳定，能处理异常情况。
4. 高效率与低存储：尽量减少内存占用和 CPU 使用。

内存和 CPU 优化示例：

• 堆内存：避免 OOM（Out of Memory）。
• CPU 占用：减少运算时间，提高速度。

---

三、算法评价指标

评价算法主要关注两个指标：

1. 时间复杂度（Time Complexity）

   • 定义：运行一个程序所需的时间。
   • 表示方法：通常用大 O 表示法（O()）。
   • 目的：衡量算法效率，越低越好。

2. 空间复杂度（Space Complexity）

   • 定义：运行程序所需的内存。
   • 目的：衡量内存消耗，减少内存使用可以降低 OOM 风险。

---

四、时间复杂度分析

1. 计算意义

时间复杂度用于衡量算法在处理大数据量时的效率，帮助我们优化代码。

2. 常见复杂度类型

类型	表示	示例	特点
常数	O(1)	哈希表（HashMap）插入、查找、删除平均是 O(1)	固定时间执行，不随数据增长
对数	O(log n)	二分查找	数据量翻倍，时间增加小。每次砍一半，数据翻倍也就多几刀，长得很慢
线性	O(n)	遍历数组	时间随数据量线性增长。一个个数数，数据多一倍，时间也多一倍
线性对数	O(n log n)	快速排序、归并排序	每个元素都要参与“砍半”，数据量大时常见的高效排序
平方	O(n²)	冒泡排序、选择排序	双重循环，一个个比，数据稍多就很慢
指数	O(n^n)	全排列问题	数据量稍大就不可行

注：
HashMap发生哈希冲突时会退化为链表 O(n) 或红黑树 O(log n)

3. 如何计算时间复杂度

1. 找循环：分析 for、while、递归等循环结构。

2. 找复杂操作：如网络请求、数据库查询等IO。

3. 同级循环计算：

   • 嵌套循环：乘法计算，循环阅读理论上越复杂

4. 优化目标

算法优化的目标是尽量让复杂度降低，靠近 O(1)：

O(1) > O(log n) > O(n) > O(n log n) > O(n²) > O(n^x)

示例：

• 列表排序：从 O(n²) 冒泡排序优化到 O(n log n) 快速排序
• O(n log n) 在教材里更常见，空格表示 log 的自变量是 n，而程序员写文档时常省略空格写成 O(n logn)。 log₂(8) = 3 ，因为 2³ = 8；log₂(1024) = 10，因为 2¹⁰ = 1024。大白话来说， log 就是问一个数能被 2 翻多少次倍得到 ，所以像二分查找的 O(log n)，就是每次把数据砍一半，大概砍几次就能找到目标。

---

五、空间复杂度分析

1. 计算意义

分析程序消耗的内存，避免浪费和 OOM。

2. 如何分析空间复杂度

1. 找占用内存的对象，如数组、链表、缓存对象。
2. 统计变量和递归调用占用的栈空间。

3. 常用优化方法

• 减少不必要的临时变量。
• 尽量复用已有内存对象。

---

六、总结

• 时间复杂度关注 速度，空间复杂度关注 内存。
• 优化算法的目标：降低复杂度，提高效率和系统稳定性。
• 现在可借助ai去编写算法，快速的降低了算法的门槛，我们可以了解下，避免ai出现幻觉，同时要多场景测试下。