@kimchan 。。。四楼的答案当然是对的，因为 return foundPos 在 for 循环体外。

话说你们没人关注一下我的代码吗？它是对的，且只遍历了一遍。

我是来搞笑的：

findpos = (lambda items, s1, s2: (lambda f: ([i for (l, i) in sorted((x for x in (f(i, v) for (i, v) in enumerate(items)) if x))] + [-1])[0])(lambda i, v: (0, i) if v == s1 else ((1, i) if v == s2 else None)))

print(findpos(['a', 'b', 'ab', 'ab'], 'ab', 'a'))
print(findpos(['a', 'a', 'b'], 'ab', 'a'))
print(findpos(['b'], 'ab', 'a'))

@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) 的结论。

@rogerchen @lxiange 你们要说的事情我知道，但是呢……

根据你们的伪代码定义，令 k=log2(n)，那么 n++, i++, i<n 三个运算都 <= O(k)。一共进行了 n 次，那么 <= O(3kn) = O(3k*2^k) = O(3n log n)。

发现了没有，你们的第一个问题是混淆了 n 和 k 。这是我说你们民间科学家的第一个原因。

第二个原因，你们混淆了理论性（理想电脑）和工程性的边界。如果按照理论性来探讨，我们可以随时随地把某些操作定义为 O(1)。再说一遍， O(1) 的操作是定义出来的，我可以定义 i++, n++ 和 i<n 三个运算为 O(1)，这不违反理论。所以在理论性的前提下，这个函数为 O(n)。

如果按照工程性来考虑，这个世界上没有无线位宽的电脑。所以位宽 k 是常数。按照你们的代码风格为 C 来考虑，这个位宽可以定义为 k=32 。所以工程性为前提，算法复杂度为 O(3kn) = O(15n)。

混淆了理论性和工程性的边界，所以说你们是民间科学家。
- - - -

别拿什么考研答案来说事，我还看不上考研这个层次的题目。

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

我喜欢 Ctrl+Space

非嵌入式领域，人工成本比硬件成本高得多。

apt-get install fcitx-*

毕竟静默报错可能会把错误累积到系统其他不知道哪里的地方，这时候查错的成本实在是大得惊人。更别说恶意攻击的情况了。

你这代码不能防御错误的 JSON 文件。现在是硬件过剩而软件复杂度超过任何人能处理的时代，宁可用大部分性能去防御错误输入，也不要假定输入是对的。显式报错永远比静默忽略要重要。

看了这张图我更进一步认为苹果干掉这么多接口是多赞的事情。

楼主好人，虽然这些我也用不上

我觉得主机的话明显黑苹果更靠谱。

@arakashic 开源社区什么时候连吐槽都不能容忍了，你这什么逻辑。

一般是不行的。

@njhuar 呃…… 其实大概 iPhone 用户不会关流量的。。。

@GhostFlying 其实不瞒你说，我很少单步调试。一般都是静态调试 + 日志纠错的。单步效率实在是太低啦，而且写稍微 premium 一点的程序就用不了单步了。比如上次我用 Scala 写 Mesos Scheduler 的时候，还有用 C++ 写一些算法的时候，根本单步不起来嘛。

最近写的程序都是 Python + TensorFlow 的，直接远程 push 到 GPU 节点上跑的，单步更加没用了，只有相信纸上推的公式和加了一堆注释的代码。。。