首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >时间复杂度:容易算错?单看循环算是不对的!

时间复杂度:容易算错?单看循环算是不对的!

作者头像
say-fall
发布于 2026-01-15 10:27:31
发布于 2026-01-15 10:27:31
2950
举报
欢迎来到say-fall的文章
在这里插入图片描述
在这里插入图片描述

🌈这里是say-fall分享,感兴趣欢迎三连与评论区留言 🔥专栏: 《C语言从零开始到精通》 《C语言编程实战》 《数据结构与算法》 《小游戏与项目》 💪格言:做好你自己,你才能吸引更多人,并与他们共赢,这才是你最好的成长方式。


前言:

我们在计算时间复杂度的时候总是喜欢看循环的次数,实际上单看循环次数是很容易出错的,下面我们来看一下


正文:

1. 什么是时间复杂度

  • 本质是算法运行时间与输入规模(通常用 n 表示)之间的增长关系,而非具体执行时间。
  • 关注 “最坏情况” 下的增长趋势,忽略常数项、低次项和系数,只保留影响最大的主导项。
  • 常用大 O 记号表示,比如 O (n)、O (log n)、O (n²),分别对应线性增长、对数增长、平方增长。

2. 时间复杂度的计算步骤

  • 确定输入规模 n:明确算法处理的数据量指标,比如数组长度、字符串长度等。
  • 找出关键操作:定位算法中执行次数最多的操作(如循环内的比较、赋值、运算),其执行次数决定了时间复杂度。
  • 统计关键操作的执行次数:分析关键操作随 n 变化的执行次数,得到一个关于 n 的表达式。
  • 简化表达式为大 O 形式:去掉表达式中的常数项、低次项和系数,只保留主导项。

3. 常见时间复杂度及示例

  • O (1)(常数阶):关键操作执行次数与 n 无关,固定不变。例:访问数组指定索引、两数相加。
  • O (log n)(对数阶):关键操作次数随 n 增长但增长缓慢,每次执行后问题规模减半。例:二分查找。
  • O (n)(线性阶):关键操作次数与 n 成正比。例:遍历数组、单层 for 循环。
  • O (n log n)(线性对数阶):n 次对数级操作的叠加。例:归并排序、快速排序(平均情况)。
  • O (n²)(平方阶):关键操作次数与 n 的平方成正比。例:双层嵌套 for 循环(如冒泡排序)。

4. 误区:以为循环的标量就是执行次数

代码语言:javascript
复制
void f(int n)
{
    int x = 0;
    for (int i = 1;i < n;i *= 2)
    {
        x++;
    }
    printf("%d\n", x);
}

int main()
{
    f(8);
    f(512);
    f(1024);
    return 0;
}

单看循环的话应该是一个O(n)的时间复杂度,因为循环了i最后的定值是n 但是需要注意的是:这里面并不是i++,而是i *= 2; 实际上每次是乘2,这就导致了执行的操作数其实是122…=n=2^x; 这样的话x = log n,也就是O(log n)的时间复杂度;

5. 以二分查找为例的对数类型时间复杂度

5.1 二分查找的两种写法
  1. 左闭右闭写法
代码语言:javascript
复制
int BinarySearch(int* nums,int numsSize,int x)
{
    //左闭右闭类型
    int left = 0;
    int right = numsSize - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == x)
            return mid;
        else if (nums[mid] > x)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}
  1. 左闭右开写法
代码语言:javascript
复制
int BinarySearch(int* nums, int numsSize, int x)
{
    //左闭右开类型
    int left = 0;
    int right = numsSize;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == x)
            return mid;
        else if (nums[mid] > x)
            right = mid;
        else
            left = mid + 1;
    }
    return -1;
}

有两种写法的原因是:二分查找的本质是区间查找

5.2 二分查找区间开闭区别总结

特性

左闭右闭 [left, right]

左闭右开 [left, right)

右边界初始化

right = size - 1

right = size

循环条件

left <= right

left < right

右边界更新

right = mid - 1

right = mid

左边界更新

left = mid + 1

left = mid + 1

区间含义

包含左右边界

包含左边界,不包含右边界

空区间条件

left > right

left == right

搜索范围

[left, right]

[left, right)

元素数量

right - left + 1

right - left

边界检查

需要检查 mid 是否在 [0, size-1] 内

需要检查 mid 是否在 [0, size) 内

5.3 二分查找的优越性与不足

对比维度

二分查找

遍历查找(线性查找)

时间复杂度

O(log n)

O(n)

空间复杂度

O(1)

O(1)

前提条件

必须是有序数组

对数据顺序无要求

查找效率

非常高效,数据量大时优势明显

效率较低,随数据量线性增长

这里举个例子说明一下,数据量大的时候二分查找究竟有多效率

数据规模

二分查找最大比较次数

遍历查找平均比较次数

10个元素

4次

5次

100个元素

7次

50次

1000个元素

10次

500次

100万元素

20次

50万次

再来看看二分查找的不足之处

不足方面

具体表现

影响程度

数据必须有序

需要预先排序,排序成本O(n log n)

高

内存访问不连续

跳跃式访问,缓存不友好

中

不适合小数据

数据量小时,优势不明显甚至更慢

低

最重要的就是,二分查找是一个数组结构的算法,这就导致了一旦有增删查改就很不方便


  • 本节完…
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2026-01-13,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 前言:
  • 正文:
    • 1. 什么是时间复杂度
    • 2. 时间复杂度的计算步骤
    • 3. 常见时间复杂度及示例
    • 4. 误区:以为循环的标量就是执行次数
    • 5. 以二分查找为例的对数类型时间复杂度
      • 5.1 二分查找的两种写法
      • 5.2 二分查找区间开闭区别总结
      • 5.3 二分查找的优越性与不足
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档