[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ⁿ）算法，
增长最快的类型之一，
你真的会开始注意到经济放缓
当你开始大量的数据。
>> 这是渐进复杂度。谢谢。