首页 > 试题广场 >

以下C代码的时间复杂度是什么？ int mystery(in

[单选题]
以下C代码的时间复杂度是什么？ 
int mystery(int n) {
    if (n == 0) 
        return 0;
    if (n % 2 == 0) 
        return mystery(n / 2);
    return 1 + mystery(n / 2);
}


  • O(log n)
  • O(n)
  • O(n log n)
  • O(n^2)
查看答案及解析
添加回答
威猛的华夫饼在备战秋招头像 威猛的华夫饼在备战秋招
  1. 函数 mystery 是递归函数，每次递归调用时，n 会除以 2（n / 2 ）。
  2. 递归的终止条件是 n == 0，递归次数取决于 n 不断除以 2 直到为 0 的次数，这个次数约为 \(\log_2 n\) ，所以时间复杂度是 \(O(\log n)\) 。
发表于 2025-08-09 11:37:48 回复(0)
牛客463327739号头像 牛客463327739号
该函数实际上计算的是 n 的二进制表示中 1 的个数（population count）。每次递归处理二进制的一位（奇数对应位为1，偶数对应位为0），并将 n 右移一位。由于二进制位数与 log2n成正比，这也印证了时间复杂度为 O(logn)。
发表于 2026-02-03 13:19:53 回复(0)
提交观点

问题信息

C语言
难度：
2条回答 103浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号