[Powered by Google Translate] 你可能听说过人们谈论的快速或高效的算法 用于执行特定的任务， 但究竟是什么，它​​意味着一种算法要快或效率吗？ 那么，它不是在谈论一个实时测量， 像几秒钟或几分钟。 这是因为计算机硬件 和软件的差异很大。 我的程序可能会遇到比你慢， 因为我较旧的计算机上运行它， 或者是因为我恰好是玩在线视频游戏 同时，这占用了我所有的记忆， 我可能会通过不同的软件运行我的程序 连通的不同的机器在一个低水平。 这就像比较苹果和桔子。 只是因为我的速度较慢的计算机需要更长的时间 比你给一个答案 并不意味着你有更有效的算法。 

所以，既然我们不能直接比较程序的运行时间 以秒或分钟， 我们应该如何比较2种不同的算法 无论他们的硬件或软件环境？ 要创建一个统一的方法来测量算法的效率， 计算机科学家和数学家们设计 测量程序的渐近复杂性的概念 和符号称为“大Ohnotation” 用于描述。 正式的定义是，一个函数f（x）的 上运行的顺序的g（x） 如果存在一些（x）的值中，x 0和 一些常数，C， 函数f（x）是小于或等于 该常数乘以克（x）的 对于所有的x比x₀。 

但是，不要被吓跑了正式的定义。 这是什么实际上意味着在更短的理论吗？ 那么，它基本上是一个方法来分析 程序的运行速度有多快的增长渐近。 也就是说，您输入的大小增加趋于无穷大， 说，你大小为10的数组排序数组的大小为1000。 你的程序运行时如何成长？ 例如，假设计数的字符数 在一个字符串中最简单的方法  走过整个字符串 信由字母，并加入1到一个计数器，用于每一个字符。 据说该算法以线性时间运行 相对于的字符数， 在字符串中的'N'。 总之，它运行在O（n）的。 这是为什么？ 那么，使用这种方法，所需的时间 遍历整个字符串 的字符数成正比。 计数20个字符的字符串中的字符数 是要采取的两倍长，因为它需要 10个字符的字符串中的字符计数， 因为你必须在所有的字符 每个字符占用相同数量的时间来看看。 当你增加的字符数， 运行时将输入长度的增加而线性。 

现在，想象一下，如果你决定了线性的时间， O（N），只为你的速度不够快吗？ 也许你存储很大的字符串， 您不能负担额外的时间，将采取 遍历所有的字符计数一。 所以，你决定尝试不同的东西。 如果你会发生在已存储的字符数 的字符串，例如，在一个变量称为“LEN”， 早在节目中， 之前，你甚至存储在字符串中的第一个字符？ 然后，所有你现在要做的，找出字符串的长度， 检查变量的值是什么。 你不会看在所有的字符串本身， 和访问的一个变量的值，如长度被认为 渐近稳定的操作， O（1）。 这是为什么？好了，记得渐近复杂性意味着什么。 如何在运行时改变的大小 您输入的增长呢？ 

假设你试图让一个大字符串中的字符数。 好吧，那就不管你有多大的字符串， 即使是100万个字符长， 你就必须这样做，这种方法找到字符串的长度， 是读出的值的变量的len， 你已经取得的。 输入长度，也就是你想查找的字符串的长度， 在不影响你的程序运行的速度有多快。 这部分程序的运行速度同样快一个字符的字符串 一千个字符的字符串， 这就是为什么这个程序将运行在固定的时间 相对于输入的大小。 

当然，也有一个缺点。 您可以在您的计算机上花费额外的内存空间 存储变量 和它需要你额外的时间 做实际存储的变量， 但问题仍然有效， 找出你的字符串多久 不依赖于在所有的字符串的长度。 因此，它运行在O（1）或固定的时间。 这当然不是意味着 您的代码运行在1步， 但无论有多少个步骤是， 如果它不与输入的大小，改变 它仍然是渐近常数，表示为O（1）。 

正如你可能已经猜到了， 有许多不同的大O的​​运行时间来衡量算法。 O（N）2比O（n）的算法，算法是渐近慢。 那就是，作为元素的数目（n）的增长， 最终O（n）的平方算法将花费更多的时间 比O（n）的算法来运行。 这并不意味着O（n）的算法，运行速度更快 比O（N）2的算法，即使是在同样的环境下， 在相同的硬件上。 也许对于小输入大小，  O（n）的平方算法实际上可能工作得更快， 但是，最终，作为输入的大小增加 趋于无穷大，O（n）的平方算法的运行时间 最终将黯然失色O（n）算法的运行时间。 就像任何二次数学函数  最终将超越任何线性函数， 不管多少头开始的线性函数开始。 如果你正在使用大量的数据， 运行的算法，在O（N）²时间才能真正结束减慢你的程序， 但对于小输入大小， 你甚至可能不会注意到。 

另外一个渐进的复杂性是， 对数时间，O（log n）的。 运行此快速算法的一个例子 是经典二进制搜索算法， 找到已排序的元素列表中的元素。 

如果你不知道什么样的二进制搜索， 我会为你解释得真快。 比方说，你要寻找的3号 在此整数数组。 它着眼于中间的元素的数组 ，问道：“是的元素，我希望大于，等于或小于这个吗？” 如果它是相等的，那么巨大的。你找到的元素，你就大功告成了。 如果是的，那么你知道元素 在阵列的右侧， 你只能看，在未来， 以及，如果是较小的，那么你知道它必须是在左侧。 然后，这个过程被重复的小尺寸数组 直到找到正确的元素。 

这个强大的算法减少一半的数组的大小与每个操作。 因此，要找到一个元素排序的数组的大小为8， 最多（登录₂8） 或这些操作， 检查的中间元件，然后切割阵列的一半，将需要 而数组的大小为16需（登录₂16）， 或4个操作。 这只是更多的一倍大小的数组操作。 阵列的大小加倍 增加了运行这段代码只有1块。 此外，检查中间的元素的列表，然后分裂。 因此，它的所述操作，在对数时间， O（log n）的。 但是等一下，你说， 这不取决于在列表中的元素，你要找的是吗？ 如果你看的第一个元素恰好是正确的吗？ 然后，只需要1操作， 不管有多大的列表。 

好了，这就是为什么计算机科学家有更多的条件 渐近复杂性，这反映在最好的情况下 和最坏情况下的性能的一种算法。 更正确地，上限和下限 在运行时。 二进制搜索在最好的情况下，我们的元素是 有权利在中间， 你得到它在固定的时间， 不管是有多大，其余的数组。 用于此的符号Ω。 因此，该算法被所述Ω（1）运行。 在最好的情况下，迅速找到该元素， 不管有多大的数组， 但在最坏的情况下， 它有执行（log n）的分裂检查 的数组中找到合适的元素。 最坏情况下的上界被称为大“O”你已经知道了。 因此，它是O（log n）的，但Ω（1）。 

的线性搜索，相比之下， 在你走过的每一个元素的数组 找到一个你想要的， 是在最好Ω（1）。 同样，第一个元素你想要的。 所以，它并不重要的数组是多大。 在最坏的情况下，它是在阵列中的最后一个元素。 所以，你必须步行通过所有n个元素的数组中找到它， 想，如果你正在寻找一个3。 因此，它运行在O（n）的时间 因为它是在数组中的元素的数目成比例。 

一个符号使用的是Θ。 这可以用来描述算法，算法的最好和最坏的情况下， 是相同的。 在我们前面谈到的字符串长度的算法就是这种情况。 也就是说，如果我们将其存储在一个变量之前 我们存储的字符串，并在固定的时间稍后访问。 不管是什么号 我们存储在该变量中，我们必须要看看它。 最好的情况是，大家看看吧 并找到的字符串的长度。 因此，Ω（1）或最好的情况下的恒定时间。 最坏的情况是， 大家看看吧，找到的字符串的长度。 所以，O（1），或固定的时间，在最坏的情况下。 因此最好的情况下，最坏的情况下，由于是相同的， 这可以说，运行在Θ（1）的时间。 

总之，我们有很好的方法，代码效率的原因有关 不知道任何事情的真实世界的时间，他们采取的运行， 这是受很多外部因素， 包括不同的硬件，软件， 或你的代码的细节。 此外，它可以让我们原因嘛，会发生什么事 当输入的大小增加。 

如果你正运行在O（n）的平方算法， 或更糟的，O（2ⁿ）算法， 增长最快的类型之一， 你真的会开始注意到经济放缓 当你开始大量的数据。 

这是渐进复杂度。谢谢。