在学习算法时，我们需要了解如何衡量算法的效率。本章后续内容会带你实现常见的排序算法和数据结构，并分析它们的性能表现。为了让初学者能够理解这些分析，这里先简要介绍时间复杂度和空间复杂度的基本概念。

基本概念

时间复杂度衡量算法执行所需的时间，空间复杂度衡量算法执行所需的内存空间。它们都用大O表示法来表示。

对于初学者，掌握以下几点就足够了：

1. 大O表示法的简化规则

• 大O表示法（如O(1)、O(n)、O(n²)、O(logn)）提供的是增长趋势的估计
• 忽略常数项和低阶项，只保留最高阶项
• 例如：O(2n² + 3n + 1) ≈ O(n²)，O(1000n + 1000) ≈ O(n)

2. 分析原则

• 通常分析最坏情况下的复杂度
• 时间复杂度越小，算法执行效率越高
• 空间复杂度越小，算法内存消耗越少

3. 简易估算方法

• 时间复杂度：主要看循环的嵌套层数
• 空间复杂度：主要看算法额外申请的数据存储空间

注意：这些方法是简化的估算方式，严谨的分析方法会在后续专门讲解。但对于理解本章内容已经足够。

实例解析

示例1：O(n)时间，O(1)空间

// 计算整数数组所有元素的和
int getSum(int[] nums) {
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
    }
    return sum;
}

• 包含单层循环遍历数组，时间复杂度O(n)
• 只使用固定数量的变量，空间复杂度O(1)

示例2：最坏情况分析

// 当n是10的倍数时计算累加和，否则返回-1
int sum(int n) {
    if (n % 10 != 0) {
        return -1;
    }
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += i;
    }
    return sum;
}

• 最坏情况下（n是10的倍数）需要执行循环，时间复杂度O(n)
• 空间复杂度O(1)

示例3：O(n²)时间，O(1)空间

// 检查数组中是否存在两数之和等于target
boolean hasTargetSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return true;
            }
        }
    }
    return false;
}

• 双层循环嵌套，时间复杂度O(n²)
• 即使可能提前返回，仍按最坏情况估算
• 只使用固定变量，空间复杂度O(1)

示例4：隐藏的时间复杂度

void exampleFn(int n) {
    int[] nums = new int[n];
}

• 创建大小为n的数组需要O(n)空间复杂度
• 数组初始化包含隐藏的循环操作，时间复杂度O(n)

示例5：O(n)时间，O(n)空间

// 返回原数组各元素的平方组成的新数组
int[] squareArray(int[] nums) {
    int[] res = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        res[i] = nums[i] * nums[i];
    }
    return res;
}

• 单层循环，时间复杂度O(n)
• 创建了与原数组等长的新数组，空间复杂度O(n)

掌握这些基本的复杂度分析方法后，你就可以继续学习后续的算法实现了。随着学习的深入，你会对这些概念有更深刻的理解！