轻松学数据结构之复杂度

本文主要介绍了算法效率分析中的时间复杂度和空间复杂度。时间复杂度衡量算法运行速度，通过大O渐进表示法估算核心操作的执行次数，常见类型包括O(1)、O(n)、O(n²)、O(2ⁿ)等。空间复杂度则评估算法临时占用的存储空间大小，同样使用大O表示法，如O(1)、O(n)等。随着计算机存储容量的提升，空间复杂度的重要性相对降低。文章通过多个代码实例（如冒泡排序、二分查找、递归算法等）具体说明了如何计算这

2401_88691476

997人浏览 · 2025-08-25 11:04:05

2401_88691476 · 2025-08-25 11:04:05 发布

文章目录

一时间复杂度:
二空间复杂度
三练习题
- 1.消失的数字
- 2.轮转数组

一时间复杂度:

1.1 时间复杂度的概念：

时间复杂度是一个数学函数，用来表示算法中基本操作执行次数与问题规模 n 之间的关系

1.2 ⼤O的渐进表⽰法

// 请计算一下func1基本操作执行了多少次？
void func1(int N){
    int count = 0;
    for (int i = 0; i < N ; i++) {
        for (int j = 0; j < N ; j++) {
            count++;
        }//N^2
    }
    for (int k = 0; k < 2 * N ; k++) {
        count++;
    }//2N
    int M = 10;
    while ((M--) > 0) {
        count++;
    }//N=10
    System.out.println(count);
}

func1 执⾏的基本操作次数：

F(N) = N² + 2N + 10

实际中我们计算时间复杂度时只需要⼤概执⾏次数，那么这⾥我们使⽤⼤O的渐进表⽰法。

规则:
1、⽤常数1取代运⾏时间中的所有加法常数。
2、在修改后的运⾏次数函数中，只保留最⾼阶项。
3、如果最⾼阶项存在且不是1，则去除与这个项⽬相乘的常数。得到的结果就是⼤O阶。

使⽤⼤O的渐进表⽰法以后，func1的时间复杂度为：

O(N²)

有些算法的时间复杂度存在最好、平均和最坏情况：在实际中⼀般情况关注的是算法的最坏运⾏情况

1.3 常⻅时间复杂度计算举例

实例1：

 // 计算func2的时间复杂度？
void func2(int N) {
    int count = 0;
    for (int k = 0; k < 2 * N ; k++) {
        count++;
    }//2N
    int M = 10;
    while ((M--) > 0) {
        count++;
    }//N=10
    System.out.println(count);
}

func2执⾏的基本操作次数：2N + 10 ,使用大O的渐进表示法 , 所以时间复杂度为：O(N)

实例2：

// 计算func3的时间复杂度？
void func3(int N, int M) {
    int count = 0;
    for (int k = 0; k < M; k++) {
        count++;
    }//M
    for (int k = 0; k < N ; k++) {
        count++;
    }//N
    System.out.println(count);
}

func3执⾏的基本操作次数：N + M
使用大O的渐进表示法

时间复杂度： O(N + M)

实例3：

// 计算func4的时间复杂度？
void func4(int N) {
    int count = 0;
    for (int k = 0; k < 100; k++) {
        count++;
    }//N=100
    System.out.println(count);
}

func4执行的基本操作次数：100
使用大O的渐进表示法

时间复杂度：O(1)

实例4：

// 计算bubbleSort的时间复杂度？
void bubbleSort(int[] array) {
    for (int end = array.length; end > 0; end--) {//N = array.length
        boolean sorted = true;
        for (int i = 1; i < end; i++) {//N = array.length-1
            if (array[i - 1] > array[i]) {
                Swap(array, i - 1, i);
                sorted = false;
            }
        }
        if (sorted == true) {
            break;
        }
    }
}

bubbleSort基本操作执行次数：
在这里插入图片描述
根据大O的渐进表示法

时间复杂度：O(n²)

实例5：

// 计算binarySearch的时间复杂度？
int binarySearch(int[] array, int value) {
    int begin = 0;
    int end = array.length - 1;
    while (begin <= end) {
        int mid = begin + ((end-begin) / 2);
        if (array[mid] < value)
            begin = mid + 1;
        else if (array[mid] > value)
            end = mid - 1;
        else
            return mid;
    }
    return -1;
}

binarySearch基本执行次数：
在这里插入图片描述

时间复杂度：O(log ₂n）

递归的时间复杂度:递归次数*每次递归代码执行次数
实例6：

// 计算阶乘递归factorial的时间复杂度？
long factorial(int N) {
    return N < 2 ? N : factorial(N-1) * N;
}

实例6通过计算分析发现基本操作递归了N次，时间复杂度为O(N)。

实例7：

// 计算斐波那契递归fibonacci的时间复杂度？
int fibonacci(int N) {
     return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

在这里插入图片描述

时间复杂度：O(2ⁿ)

二空间复杂度

算法运行过程中额外使用的存储空间规模

实例1：

void bubbleSort(int[] array) {
    for (int end = array.length; end > 0; end--) {
        boolean sorted = true;
        for (int i = 1; i < end; i++) {
            if (array[i - 1] > array[i]) {
                Swap(array, i - 1, i);
                sorted = false;
            }
        }
        if (sorted == true) {
            break;
        }
    }
}

实例1使⽤了常数个额外空间，所以空间复杂度：O(1)

实例2：

 // 计算fibonacci的空间复杂度？ 
int[] fibonacci(int n) {
    long[] fibArray = new long[n + 1];
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n ; i++) {
       fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }
    return fibArray
 }

只需要“第 n 个”斐波那契数，而不是整个数组,所以空间复杂度：O(n)

实例3：

 // 计算阶乘递归Factorial的空间复杂度？
long factorial(int N) {
   return N < 2 ? N : factorial(N-1)*N;
}

实例3递归调⽤了N次，开辟了N个栈帧，每个栈帧使⽤了常数个空间。空间复杂度为O(N)

三练习题

1.消失的数字

在这里插入图片描述
解法一:

public int missingNumber(int[] nums) {
    int n = nums.length;
    // 1. 计算 0 到 n 的理想总和
    int expectedSum = n * (n + 1) / 2;
    
    // 2. 计算数组中现有数字的实际总和
    int actualSum = 0;
    for (int num : nums) {
        actualSum += num;
    }
    
    // 3. 差值即为缺失值
    return expectedSum - actualSum;
}

2.轮转数组

在这里插入图片描述

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n; // 步骤1：防止 k 大于数组长度

        // 步骤2：翻转整个数组
        reverse(nums, 0, n - 1);
        // 步骤3：翻转前 k 个元素
        reverse(nums, 0, k - 1);
        // 步骤4：翻转后面剩余的元素
        reverse(nums, k, n - 1);
    }

    // 辅助函数：翻转数组中从 start 到 end 的部分
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}