民宿网络营销方式_市政府门户网站_湖北网络营销网站_域名比价网

算法 1：原地交换数组元素

for(int i=0; i < n/2; i++) {t = a[i];               // 取出第 i 个元素a[i] = a[n-i-1];        // 把倒数第 i 个元素放到前面a[n-i-1] = t;           // 把原来的第 i 个元素放到后面
}

时间复杂度分析

1. 循环次数：循环从 i=0 到 i < n/2，总共执行 n/2 次。
   • 例如：如果 n=6，循环执行 3 次（i=0,1,2）；如果 n=5，循环执行 2 次（i=0,1）。
2. 每次循环的操作：每次循环内部有 3 次赋值操作（交换两个元素），这些操作的时间是固定的（常数时间）。
   • 总操作次数 = 3 * (n/2) ≈ 1.5n → 用大 O 表示法简化为 O(n)（忽略常数系数）。

空间复杂度分析

• 额外空间：只用了一个临时变量 t，无论数组多大，只需要 1 个变量的空间。
  • 因此空间复杂度是 O(1)（常数空间）。

---

算法 2：借助辅助数组反转

// 步骤 1：将数组 a 逆序存入数组 b
for(int i=0; i < n; i++)b[i] = a[n-i-1];   // 把 a 的最后一个元素放到 b 的第一个位置，依此类推// 步骤 2：将数组 b 复制回数组 a
for(int i=0; i < n; i++)a[i] = b[i];       // 把 b 的内容覆盖到 a

时间复杂度分析

1. 第一个循环：执行 n 次，每次赋值操作，时间复杂度 O(n)。
2. 第二个循环：同样执行 n 次，时间复杂度 O(n)。
   • 总时间 = O(n) + O(n) = O(n)（大 O 表示法忽略常数倍数）。

空间复杂度分析

• 额外空间：需要创建一个和原数组 a 大小相同的数组 b，长度为 n。
  • 因此空间复杂度是 O(n)（空间随输入规模线性增长）。

---

对比与例子

例子：假设 n=5，数组 a = [1,2,3,4,5]

算法 1 的执行过程（原地交换）

1. i=0: 交换 a[0] 和 a[4] → [5,2,3,4,1]
2. i=1: 交换 a[1] 和 a[3] → [5,4,3,2,1]
3. 结束（循环执行 2 次，n/2=2.5 → 取整为 2）。

算法 2 的执行过程（借助辅助数组）

1. 创建数组 b，长度 5。
2. 第一个循环：
   • b[0] = a[4] = 5
   • b[1] = a[3] = 4
   • b[2] = a[2] = 3
   • b[3] = a[1] = 2
   • b[4] = a[0] = 1
     → b = [5,4,3,2,1]
3. 第二个循环：将 b 复制回 a → a = [5,4,3,2,1]。

---

为什么算法 1 更高效？

1. 时间：两者都是 O(n)，但算法 1 的循环次数是 n/2，算法 2 是 2n，实际运行更快。
2. 空间：算法 1 不需要额外数组，节省内存，尤其是处理大规模数据时优势明显。

---

总结

	时间复杂度	空间复杂度	适用场景
算法1	O(n)	O(1)	内存敏感，大数据量
算法2	O(n)	O(n)	逻辑简单，小数据量

优先选择算法1，除非你需要保留原数组（算法2中 b 可以保留逆序结果）。