如果我有未分类的数字阵列和一些我在寻找，我相信没有检查的方式，如果我的电话号码是它除了通过每个成员会的算法复杂性并进行比较。检查是否在数组中存在的元素
现在，在数学和各种理论分支我一直感兴趣的，有常，你通常得到你放什么图案。我的意思是，通常有每一个意想不到的结果的解释。以蒙蒂霍尔问题为例。直到你意识到主机增加了更多的信息，因为他知道汽车后面是什么门，这似乎是反直觉的。
既然你迭代，而不是刚开是或否的答案阵列上，你也可以得到元素的确切位置（如果它的存在）。那么不是说有一个算法不那么复杂，而只给你一点信息？
我完全脱离基地吗？
有信息你得到的量和算法的复杂性之间的实际关系？从算法获得的信息量与其复杂性之间的关系背后的理论是什么？
当你正在寻找一个数组，索引是一分钱一分货具有阵列的价格。通过索引访问元素的能力是数组结构中固有的：换句话说，一旦你说“我要搜索数组”（不是集合，但特别是数组），你已经为索引支付了费用。在这一点上，没有办法摆脱它，并且与搜索数组相关的成本。
但是，这不是唯一的解决方案：如果您同意放弃索引作为需求的能力，您可以构建一个集合，以更快的速度为您提供yes/no的答案。例如，如果您使用散列表，则搜索时间将变为O(1)。当然，哈希表中没有关联的索引：无法以任意顺序访问项目是您支付能够在一段时间内检查是否存在项目的能力。
对！这完全滑了我的脑海。数据结构的选择限制了我对复杂性的“细粒度控制”的数量。 – 2014-09-06 19:10:30
是的，你完全大错特错，对不起！
算法复杂度是根据解决大小为N的问题需要多少操作来定义的。如果数组中有N个元素，则无法确定该值是否出现在数组中，而不是检查所有N个元素。这使得它是线性的，或者O（N）。
事实上，你可以也确定值的位置在O（N）（事实上你可以）并不意味着你可以在更短的时间内解决更简单的问题。
这太糟糕了。我希望在理论上会有更多。我猜栈溢出不是真正的讨论和开放式问题的地方。谢谢你的回答。 – 2014-09-06 19:04:37
@LukaHorvat最后一段涉及到底层理论。问题出现在*硬度的阴影*中：必须花费多少资源来解决问题的实例？这不是一个严格的顺序：即使一个（如果在任何地方，这个数组中的这个值是什么），许多问题都是相同的，而且这个问题比另一个更普遍（这个值是否出现在这个数组中？）。这些问题中的每一个都可以被证明具有一些特定的复杂性，而且这两个问题的证明几乎完全相同。看到有这样的证据，你的问题并不是真正的开放性的。 – delnan 2014-09-06 19:11:07
什么是单点信息？ – thumbmunkeys 2014-09-06 18:59:15
对不起，我不明白这里有什么问题。 – gd1 2014-09-06 18:59:24
@thumbmunkeys问题的答案是“这个数组是否在这个数组中？” – 2014-09-06 19:00:34