来看看这个函数的时间复杂度是多少

你如果用你这一套理论，你会对大量算法顶会文章的复杂度计算产生疑惑。

时间复杂度为 O （ n ）

@lxiange 你说的这些概念在算法课上老师都会提到，但是最后老师会说我们一般考虑"加法的时间复杂度是 O(1)"
在这个前提之下才会有这些题目。

@reus 还是平常我们对概念理解不够清楚的，平常遇到的大部分是多项式时间的，按那种方式定义 n 恰好结论一致。我希望你能自己看一下我上面贴的那篇 so
http://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time

When working with algorithms that process graphs, lists, trees, etc., this definition more or less agrees with the conventional definition. For example, suppose you have a sorting algorithm that sorts arrays of 32-bit integers. If you use something like selection sort to do this, the runtime, as a function of the number of input elements in the array, will be O(n2). But how does n, the number of elements in the input array, correspond to the the number of bits of input? As mentioned earlier, the number of bits of input will be x = 32n. Therefore, if we express the runtime of the algorithm in terms of x rather than n, we get that the runtime is O(x2), and so the algorithm runs in polynomial time.

说到底最终还是歧义的问题，不是思维的问题。

@jsq2627 他这道题目还是很直白的，普通人都不会认为有歧义

@laxenade @rogerchen 首先对于“民间科学家”的不当言论表示歉意。但是我仍然有话反驳。

先列出结论：我认为就你们举的这个例子，无论是 O(n) 还是 O(n log2 n) 都是逻辑自洽的，其中 O(n log2 n) 的论述见我之前的回复。当令 k = log2(n)，可得 O(2^k * k)。然而在这里如果我想要把 k 代换成 n 给出 O(2^n * n) 的复杂度就是不恰当的，因为 n 在上下文是有明确含义的，不能把一个符号随意变换含义。

所以对于 O(2^n) 的这个结论，如果按照 n 表示 k 的角度去看，就少了一个 *k 的因子；如果不是这样，那就显然更加离谱了。
- - - -

@rogerchen 对于你说的复杂度分析不应该考虑工程问题，这显然不合适。我们目前的算法都是为了电子计算机设计的，因此所有算法分析和时间复杂度估计都是在电子计算机的前提下成立的；这已经考虑了工程问题。

@laxenade 你说“限制 32bit 的话，那就都变成 O(1)了”，只是大 O 。就算是考虑 32 位整数，在这个例子里面，当限定 n 为 32 位整数， O(15 n) （见我先前的回复）依旧是比 O(15 * 2^32) 更紧的界。同时，算法的复杂度不会小于 Ω(n)。因此 Ω(n) 和 O(15 n) 卡住了这个算法在 32 位整数下的界，因此 Θ(n) 是紧界。

当然如果按照教科书的定义，一切 n < ∞ 的论述都是没有意义的。可是啊，读书不能死扣概念，要领会它的精神。复杂度分析是为了在没有测试算法的前提下估计它的运行时间，当我们有了 32 位整数的大前提下，考虑更细致的界依旧是有意义的，因为我们可以通过计算来估计两个不同算法的优劣。
- - - -

@rogerchen @laxenade 另外还有第二点反驳。你们可能不赞同我说的，“可以定义 i++, sum++, i<n 三个操作为常数时间”。然而你们是出于电子计算机的前提才这么反驳我的。我们谁也不知道将来的量子计算机，乃至什么其他种类的计算机究竟能够有多快，因此我假设这三个操作是 O(1) 是公理，完全不违背理论性。

如果接受这三个假设，那么你们的算法复杂度是 O(n) 是没有错误的结论。当然如果不接受，认为这三个操作的复杂度是 O(log2 n)，那么推出来的结论就是 O(n log2 n)。

当我们考虑 32 位定长整数的电子计算机的时候，也可以认为上述三个操作为 O(1)，得出 O(n) 的结论。

@jsq2627 为什么我要用 1111 来表示 16 ，而不能用 16 个 1 来表示？ 讨论到特定的输入形式了，那是需要先定义清楚条件的。

哪个指令集的整型加减不是 O(1)？好好的一个 C 程序，怎么就扯到计算理论和图灵机上去了？

最后再回复一条，就不一一 @了

其实退一步讲，这并不是一个多么值得探究的问题。
本质上来说，只是消歧义罢了，毕竟大家都知道程序运行起来要多长时间（怪我把函数的参数起名为 n ），
即便这样，是 O(n)还是 O(2^n)，也取决于看待输入的方式。一般定义大 O 表示法的 n 为输入的 length ，
但是大家一般都默认单参数时，把输入的参数的值作为 n ，虽然它和输入的 length 相差了一个指数级。

平时交流、答题时，还算遵守大家的习惯约定就好，具体应该是什么有时反而不重要了。
不然每次讨论几何问题时都要带上 5 条公理，讨论集合问题时都要带上 ZFC 公理，岂不是很累？

和大家撕逼撕得很开心，哈哈~

预祝各位新年快乐！

@lxiange 你的错误在于你已经在题目中指定 n 是什么了，还在重用这个符号表示另一个概念，并且不定义 n 是什么。不定义符号摆公式是很民科的行为，就酱。

O(N)

OVER （滑稽脸）

自作聪明，自以为是，自取其辱

@rogerchen 哈哈，你是哪个学校的？ ppt 看着眼熟啊

看不下去了， 楼主一共贴了三段代码：

void foo1(int n) {
int bar = 0;
for (int i = 0; i < n; i++) {
bar++;
}
}

void foo1(int n) {
int bar = 0;
for (int i = 0; i < n; i++) {
bar += i++;
}
}

void foo(int n) {
int sum = 0;
int i = 0;
while (sum < n) {
sum += i++;
}
}

三段代码不完全等同。 我个人认为时间复杂度分别为 O(n), O(sqrt(n)),O(sqrt(n))

当看到题主说这是考研 408 的题目我当时震惊了。
考研层次的知识被尝试用计算理论去解释它是不合适的。 408 的考察范围也绝不会涉及到这些内容，不然就是命题人的失职 。就像我们看中学数学中介绍的负数不能被开方一样。这些讨论都是有默认的讨论环境的。

@sadscv 所以我对题主给出的根号 n 的复杂度答案也很疑惑。直到我看某楼贴出来的真正的题目。题主你个标题党，绝对是过度解答了这个问题！！！

我支持 gcc 全优化编译答案是 O(0) XD

我暗想我和掌柜的等级还很远呢，而且我们掌柜也从不将茴香豆上账。

默认情况是 O(n)
如果 n 是常数，开了编译器优化后是 O(1)，这玩意在编译阶段就给算出来了