「IXOI R3」时间复杂度分析

GitHub跳转原题关系图Canvas 关系图返回列表

比较 n、n^2 与 5×10^8 的关系，按复杂度从高到低输出能够通过的最高级别。

OJ: luogu

题目 ID: P17413

难度:入门

标签:复杂度数学

日期: 2026-09-06 19:06

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结

形式化题目

给定正整数 n。允许的复杂度只有 O(1)、O(n)、O(n^2)，一次运算上限为 5×10^8。 求能够在该上限内完成的最高复杂度。

正解

思路

把三种复杂度对应的运算次数分别写出来：

  • O(1)O(1) 需要 11 次，永远可以通过；
  • O(n)O(n) 需要 nn 次，当 n⩽5×108n \leqslant 5\times 10^8 时可以通过；
  • O(n2)O(n^2) 需要 n2n^2 次，当 n2⩽5×108n^2 \leqslant 5\times 10^8 时可以通过。

因此按复杂度从高到低判断即可。平方判断不能直接计算 n2n^2，因为 nn 最大可达 101810^{18}；使用 n⩽(5×108)/nn \leqslant (5\times 10^8)/n 可以避免溢出。

这里没有独立的暴力到正解过程：朴素做法与正解都只是比较三个运算次数，唯一需要优化的是避免计算可能溢出的 n2n^2。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-06 19:06
 * update_at: 2026-09-06 19:22
 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;

    // 先判断平方复杂度，再判断线性复杂度，常数复杂度总能通过。
    if (n <= 500000000LL / n) {
        cout << "O(n^2)\n";
    } else if (n <= 500000000LL) {
        cout << "O(n)\n";
    } else {
        cout << "O(1)\n";
    }
    return 0;
}

复杂度

只进行常数次判断，时间复杂度为 O(1)O(1)，额外空间复杂度为 O(1)O(1)。

总结

本题的关键是先判断更高的复杂度。比较乘积时要注意整数溢出，利用 n⩽C/nn \leqslant C/n 就能安全判断 n2⩽Cn^2 \leqslant C。