全文共字，预计学习时长3分钟

过去几个月我一直在学习软件开发，常常会注意到一些开发概念。就在最近，我偶然发现了一个最疯狂的故事。

这个故事发生在十多年前，一家使用慢速互联网的公司想出了一个主意：使用世界上最耗时的互联网传输大量数据，并与信鸽竞速，目的地是他们约50英里外的办公室。当然，我和大多数人想的一样，他们实在是闲得慌，信鸽怎么可能打败互联网。

故事中常见的反转发生了，处于劣势的一方胜出，信鸽成功地占了上风。但我的第一反应依然是：“这太荒谬了。我从没听说过这样的事情。这不可能！”但随即我又想到之前给别人发送一个30分钟的视频时，上传和传输有多么复杂。

信鸽和互联网的整个故事引出了算法效率的概念，也就是“BigO”。

当我现在回想那个故事时，很容易看出信鸽是多么忠实地在运输。不管信鸽运送的是什么，它们的飞行路线都是一样的（不考虑恶劣天气）。然而，互联网与之大相径庭，传输时间与数据多少密切相关。

那么传输时间和数据多少的关系究竟是什么样的呢？BigO就是关于输入变量的运行时间尺度。信鸽的传输速度表示为O(1)，而大量的互联网传输时间表示为O(N)。

下面是关于“BigO”和标准增长顺序的一些常见例子。

需要注意的一点是，BigO总是假设上限，即认为算法将执行最大次数的迭代。

O(N)是一种算法，它会线性增长，并且与数据集大小成正比。它将决定函数是在读取完第一个元素后返回true，还是在读取完等式的所有项后返回false。

它代表一个函数，其算法与输入规模的平方成正比。当增加更多嵌套迭代时，输入规模可能会变大，这只会增加等式的复杂性，也可以进行三次或者四次迭代。

O(1)非常简单，它代表的函数不管输入次数是多少，取值总是保持不变。

它代表的函数对于输入中的每个元素，函数性能将翻倍。该函数对每个输入数字递归调用两次，直到它小于或等于1。其中一个例子是斐波那契数列，其通过将前面两个数字相加得到下一个数字实现一串数字的迭代。

(2，2，4，6，10，16，26，42…)

最后，还有O(logn)，在此我不再赘述了。如果你对算法或分析其整体可扩展性和效率感兴趣，那么建议你继续深入了解BigO。

留言点赞

转载请注明:http://www.aideyishus.com/lkzp/1553.html