如果我有一个算法，输入只是一个数字，输出是它的一组除数。所以我的输入将永远是一个数字，算法中的迭代次数将取决于数字有多大。会是什么这种算法的大符号？算法：
1: Set m := 2.
2: Set S := {} for S a multi-set.
3: while m <= n^0.5
do
4: if m divides N then
5: Set S U m
6: else
7: Set m = m + 1.
8: end if
9: end while
10: Return the set S of divisors found.
您可以让用于渐近复杂度的大 O 表示法中的变量是输入数字本身，也可以是表达该数字所需的位数。这两种约定产生了截然不同的渐近分类，因此在报告结果时明确使用哪一种非常重要。
一般来说，当人们谈论数字太大以至于需要 bignums 的情况时，人们倾向于使用位数约定，而当输入受大小限制时，他们倾向于使用数字含义约定。机字。但这不是您可以依赖的东西，只能获得第一个猜测，您需要自己验证在您的特定情况下是否有意义。
选择往往与您用于算术运算的成本模型密切相关。当您计算位时，通常假设对 n 位值的算术需要 O(n) 时间，而当您处理输入数字的含义时，您通常假设对数字的算术在恒定时间内工作。
在你的情况下，你会得到类似 O(2^n) 或 O(sqrt(m)) 的东西，其中 n 是输入中的位数， m 是输入本身。（细节取决于你的多集基元如何执行）。
另见伪多项式时间。