大三备战考研 + 找实习：我整理了 20 道必会的时间复杂度题（建议收藏）

最近在准备 考研 + 找实习，复习数据结构的时候发现一件事：

很多同学会写代码，但一问 时间复杂度 就开始沉默。

比如：

for(i=0;i<n;i++)
   for(j=0;j<n;j++)

时间复杂度是多少？

有人说 O(n²)，没问题。

但如果稍微变一下：

for(i=1;i<n;i*=2)

很多人就懵了。

而实际上，时间复杂度是考研和面试的高频考点。

所以我整理了 20 道经典时间复杂度题，难度不高，但非常有代表性。

如果你是：

• 准备 考研408
• 准备 找实习面试
• 或者 想打好数据结构基础

建议认真看一遍。

一、什么是时间复杂度？

简单来说：

时间复杂度就是：算法执行次数随着输入规模 n 增长的变化趋势。

我们一般用 大 O 表示法（Big-O） 表示。

常见复杂度排序：

O(1)     常数级
O(log n) 对数级
O(n)     线性级
O(n log n)
O(n²)
O(n³)
O(2^n)
O(n!)
O(n^n)

效率从高到低依次下降。

二、20 道经典时间复杂度题

1 基础循环

for(int i=0;i<n;i++){
    printf("hello");
}

执行次数：

n

时间复杂度：

O(n)

2 双重循环

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        printf("hi");
    }
}

执行次数：

n × n

时间复杂度：

O(n²)

3 不同变量循环

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        printf("hi");
    }
}

执行次数：

n × m

时间复杂度：

O(nm)

4 三重循环

for(int i=0;i<n;i++){
   for(int j=0;j<n;j++){
       for(int k=0;k<n;k++){
           printf("hi");
       }
   }
}

执行次数：

n³

时间复杂度：

O(n³)

5 循环减半

for(int i=n;i>0;i/=2){
    printf("hi");
}

变化过程：

n
n/2
n/4
n/8

执行次数：

log₂ n

时间复杂度：

O(log n)

6 倍增循环

for(int i=1;i<n;i*=2){
    printf("hi");
}

变化过程：

1
2
4
8
16

执行次数：

log₂ n

时间复杂度：

O(log n)

7 n + log n

for(int i=0;i<n;i++){
    printf("a");
}

for(int j=1;j<n;j*=2){
    printf("b");
}

复杂度：

O(n + log n)

根据 大O法则取最大项

最终：

O(n)

8 嵌套对数循环

for(int i=0;i<n;i++){
    for(int j=1;j<n;j*=2){
        printf("hi");
    }
}

执行次数：

n × log n

复杂度：

O(n log n)

9 三角循环

for(int i=0;i<n;i++){
    for(int j=0;j<=i;j++){
        printf("hi");
    }
}

执行次数：

1 + 2 + 3 + ... + n

这是经典公式：

1 + 2 + 3 + ... + n = n(n+1)/2

时间复杂度：

O(n²)

10 减少型嵌套循环

for(int i=0;i<n;i++){
    for(int j=i;j<n;j++){
        printf("hi");
    }
}

执行次数：

n + (n-1) + (n-2) + ... + 1

复杂度：

O(n²)

11 while + n 减半

while(n>1){
    n = n/2;
}

执行次数：

log₂ n

复杂度：

O(log n)

12 递归减半

void f(int n){
    if(n<=1) return;
    f(n/2);
}

递归深度：

log₂ n

时间复杂度：

O(log n)

13 二分查找

while(l <= r){
    mid = (l+r)/2
}

每次缩小一半。

复杂度：

O(log n)

这是 所有面试必问算法之一。

14 递归二叉分裂

T(n) = 2T(n/2) + O(1)

复杂度：

O(n)

这是经典的 分治递归。

15 归并排序

递归公式：

T(n) = 2T(n/2) + O(n)

复杂度：

O(n log n)

16 快速排序平均复杂度

平均：

O(n log n)

最坏：

O(n²)

17 冒泡排序

for(i=0;i<n;i++)
   for(j=0;j<n-i;j++)

复杂度：

O(n²)

18 插入排序

最坏情况：

O(n²)

最好情况：

O(n)

19 顺序查找

遍历数组：

0 → n

复杂度：

O(n)

20 哈希查找

平均复杂度：

O(1)

最坏情况：

O(n)

三、面试和考研最爱考的 5 个复杂度

如果时间不多，至少记住这 5 个：

四、如何快速判断时间复杂度？

给大家总结 4 个实用技巧：

1 看循环层数

1层 → O(n)
2层 → O(n²)
3层 → O(n³)

2 看变量变化

i++
→ O(n)

i*=2
→ O(log n)

3 递归看递归树

常见三种：

T(n)=T(n-1)  → O(n)
T(n)=T(n/2)  → O(log n)
T(n)=2T(n/2) → O(n)

4 只保留最高阶

例如：

O(n² + n + 100)

最终：

O(n²)

五、写在最后

数据结构其实没有想象中那么难。

真正难的是：

没有系统刷题。

如果你：

• 准备 考研408
• 准备 算法面试
• 或者和我一样 大三准备找实习

建议：

把时间复杂度题至少练 50 道。

很多算法题其实第一步就是：

先分析复杂度。

如果这一步不会，代码基本也写不出来。

如果这篇文章对你有帮助，可以：

• 点个 赞 👍
• 收藏 ⭐
• 转发给一起准备考研 / 找实习的同学

后面我也会继续整理：

• 30 道经典链表题
• 二叉树面试必刷题
• 考研数据结构高频考点

一起加油。

大三这一年，真的很关键。

本文由mdnice多平台发布