更多相关内容可查看

1. 什么是时间复杂度？

时间复杂度（Time Complexity）是衡量算法执行时间随输入规模（n）增长的变化趋势的指标。在Java中，我们使用大O表示法（Big-O Notation）来描述时间复杂度，它关注的是最坏情况下的增长率。

为什么需要时间复杂度？

• 帮助我们比较不同算法的效率。
• 预测算法在数据规模增大时的性能表现。
• 优化代码，避免写出低效的算法。

---

2. 常见时间复杂度对比

时间复杂度	示例（Java代码）	适用场景
O(1)	arr[0] = 10;	直接访问数组/哈希表
O(log n)	while (n > 0) { n /= 2; }	二分查找、分治算法
O(n)	for (int i = 0; i < n; i++)	遍历数组/链表
O(n log n)	Arrays.sort(arr)	快速排序、归并排序
O(n²)	for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) }	冒泡排序、选择排序
O(2ⁿ)	int fib(int n) { return fib(n-1) + fib(n-2); }	递归计算斐波那契数列
O(n	全排列问题	暴力搜索

---

3. 如何分析时间复杂度？（Java版）

🔹 步骤1：找出基本操作

在Java中，基本操作通常是：

• 循环内的操作（如 for、while）
• 递归调用
• 数学运算（如 i++、i *= 2）

示例1：计算数组和

int sum = 0;
for (int num : arr) {  // 基本操作：sum += numsum += num;
}

• 时间复杂度：O(n)（遍历整个数组）

---

🔹 步骤2：分析循环结构

（1）单层循环 → O(n)

for (int i = 0; i < n; i++) {System.out.println(i);
}

• 时间复杂度：O(n)

（2）双层循环 → O(n²)

for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.println(i + "," + j);}
}

• 时间复杂度：O(n²)

（3）循环次数减半 → O(log n)

int i = 1;
while (i < n) {i *= 2;  // 每次循环i翻倍
}

• 时间复杂度：O(log n)

---

🔹 步骤3：递归算法分析

递归的时间复杂度通常用递归树或**主定理（Master Theorem）**分析。

（1）斐波那契数列（O(2ⁿ)）

int fib(int n) {if (n <= 1) return n;return fib(n-1) + fib(n-2);
}

• 时间复杂度：O(2ⁿ)（指数级增长）

（2）归并排序（O(n log n)）

void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);      // T(n/2)mergeSort(arr, mid + 1, right); // T(n/2)merge(arr, left, mid, right);   // O(n)}
}

• 递归公式：T(n) = 2T(n/2) + O(n)
• 时间复杂度：O(n log n)

---

4. 常见误区

❌ 误区1：认为所有循环都是O(n)

for (int i = 0; i < 1000; i++) {System.out.println(i);
}

• 正确复杂度：O(1)（循环次数固定，不随n增长）

❌ 误区2：忽略内置方法的时间复杂度

List<Integer> list = new ArrayList<>();
list.add(0, 10);  // ArrayList的add(0, x)是O(n)！

• 正确复杂度：O(n)（因为要移动所有元素）

❌ 误区3：混淆平均复杂度和最坏复杂度

• 快速排序：
  • 平均：O(n log n)
  • 最坏：O(n²)（当数组已经有序时）

---

5. 实战训练

题目1：计算以下代码的时间复杂度

for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {System.out.println(j);}
}

• 答案：O(n²)（内层循环次数从n到1，总和≈n²/2）

题目2：分析递归函数的时间复杂度

void foo(int n) {if (n <= 1) return;System.out.println(n);foo(n / 2);foo(n / 2);
}

• 递归公式：T(n) = 2T(n/2) + O(1)
• 时间复杂度：O(n)（可用主定理计算）

---

6. 总结

关键点	说明
O(1)	哈希表查询、数组随机访问
O(log n)	二分查找、分治算法
O(n)	遍历数组、线性搜索
O(n log n)	快速排序、归并排序
O(n²)	冒泡排序、暴力搜索
O(2ⁿ)	递归计算斐波那契数列
O(n	全排列问题

📌 最终建议：

1. 在写代码前先分析时间复杂度。
2. 避免写出 O(n²) 或更高的算法（除非数据量很小）。
3. 面试时，能用 O(n) 解决的问题，不要用 O(n²)。

---

📖 推荐阅读

• 《算法导论》（Introduction to Algorithms）
• 《Java数据结构和算法》（Data Structures and Algorithms in Java）
• LeetCode 刷题（按难度和标签分类练习）