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

@xcatliu 哦这样, n 一般都得自己解释啊，" I think the time complexity of this function is 2^n where n represents the length of the input array..."

唉，浪费我时间

@nagato
@xcatliu
前面说过，这种理论问题用编程是不能证明的。不然大家赶紧跑去证明 P!=NP 了，
这个问题的本质歧义就在于 n 的定义上，你可以看一下我前两条回复。看看哪种定义 n 才会引起混乱。
关于 n 的定义，不是自己想怎么认为就怎么认为的，维基百科（ https://en.wikipedia.org/wiki/Time_complexity ）上说得很清楚：
“ In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the **length of the string representing** the input.”
大伙儿真有把 n 当成“ string representing ”来看么？

@Perry 之前贴了链接了，自己看。可以把引用来源的书拿来看一看。

@sudoz 就是考研的科目编号而已。

樓主民科鑑定完畢。
就是 O(n)，沒有疑義。整個算法的執行次數和 n 的大小呈線性關係，再扯其他的都是在扯蛋。

@lxiange 你这个 foo5 什么叫 "输入大小几乎一样"

@lxiange 引起混乱的是你对“输入大小”的错误理解。
比如数字 7 ，你觉得输入就是 111 吗？
我可以让输入是 1000101010 ，我想怎么输入就怎么输入。只要我对图林机读取的逻辑有完整的定义。

偷换概念

还可以这样装 X...66

所以说选根号 n 是可以得分的吧。。。

我来给楼主解释一下，这里 int 我们一般人认为是固定字节长度，所以一次加法操作算是 O(1)
如果 int 是大数，则楼主的说法可以成立，显然楼主可能并不懂我在说什么

楼主是对的，这题跟整数价格 0-1 背包伪多项式时间 O(mn) 一样。多项式时间和伪多项式时间不是一个概念。 RAM 计算模型读入一个 64bit 的数只需要 32bit 的数一倍的时间，但是这个程序需要跑平方那么多的时间，不就是 O(2^n)。平时说的排序 O(nlogn)，读的可是 n 个数。仔细思考一下，不要给人乱扣什么民间计算机科学家的帽子。

@lxiange 大 O 表示法的 n 是输入规模啊，大哥，输入规模，输入规模，输入规模

重新定义时间复杂度系列？

按你这么说，输入 15 不应该是 1111 ，而是 00000000000000000000000000001111
任何 int 都是 32 位的，输入规模是常数。

连题都不是同一个题……

看楼中间的那位，都有些无语了

一个民间计算机科学家的钓鱼贴你们也回得这么起劲干嘛。

@lxiange 你英语有问题
另外你搞错了，我想你应该参考的是 Big O 的解释
https://en.wikipedia.org/wiki/Big_O_notation

大家散了吧，肯定是题主考研写错题了，出来安慰自己，大 O 这些算法入门课第一讲的东西。

题主不要灰心啦，一选择题而已。说不定大题有更大的惊喜等着你哟。

@lxiange 本科计算理论主要就分两块，可计算性和复杂性，当然都是基于图灵机的。

LZ 用了一个很巧妙的办法把自己绕进去了，就是 用 1111 来 代表了 15 ，推出复杂度是 2^N ，然而从 1111 计算出 15 这个过程就是 2^N 的，如果我直接用 15 个 1 来代表输入，那复杂度还是 N 啊