在计算算法运行时间的问题中，对于输入元素个数为N的算法，可以考虑其运行所需最大时间T(N)，也称输入元素个数为N时的最坏情况下运行时间。为了进一步简化问题，不寻求T(N)的精确值，而主要考察T(N)在N较大时的特点，我们要找的是函数T(N)形式比较简单的上界函数，比如对于某个常量c和任意大的N，可以有T(N)<= cN。对于这种情况，可以肯定“在最坏情况下，运行时间也可以与输入元素个数成正比”，当算法在不同计算机上运行时，取不同的常数c，因此还可以进一步简化表达式，使其不再含有常数c，用大O表示法，前面的关系式写成T(N)=O(N)，通常，如果存在某个函数f使得T(N)<=cf(N)，那么对于某个常量c和任意大的N，我们定义T(N)=O(f(N))
这段话其实是计算机科学中算法复杂度分析（大O表示法）的核心逻辑。它解释了为什么程序员在聊代码快慢时，不聊“几分几秒”，而是聊 \(O(N)\) 或 \(O(N^2)\)。
原文： 对于输入元素个数为N的算法，可以考虑其运行所需最大时间T(N)，也称输入元素个数为N时的最坏情况下运行时间。
通俗解读：
假设你要在一堆乱序的扑克牌（共 \(N\) 张）里找一张红桃A。
在实际算算法时间时，最好情况毫无意义（谁能保证每次运气都好？），平均情况计算极其复杂（需要数学概率论）。只有最坏情况 \(T(N)\) 最好用，它相当于给算法兜底：“无论输入多极端，这个算法最慢也就是 \(T(N)\) 这么长，绝不会更慢了。” 这种确定性让工程师最安心。
原文： 为了进一步简化问题，不寻求T(N)的精确值，而主要考察T(N)在N较大时的特点，我们要找的是函数T(N)形式比较简单的上界函数……
通俗解读：
假设我们精准测量了某个算法在电脑上的运行步数，得到精确函数是 \(T(N) = 3N^2 + 5N + 10\)。
当 \(N\) 变得非常大时（比如处理海量用户数据，\(N = 1,000,000\)）：
瞧见了吗？在大数据面前，后两项 \(5N\) 和 \(10\) 连零头都算不上！真正决定这个算法运行时间的，是那个最高次项 \(N^2\)。
因此，科学家决定抓大放小。既然精确值这么难算，不如找一个形式简单的“天花板”（上界）。只要在 \(N\) 很大时，这个天花板能罩住 \(T(N)\) 就行了。
原文： 当算法在不同计算机上运行时，取不同的常数c，因此还可以进一步简化表达式，使其不再含有常数c，用大O表示法……
通俗解读：
同一段找扑克牌的代码：
如果把电脑硬件的差异算进去，我们就没法纯粹地比较“算法本身的好坏”了。
为了让算法评级脱离硬件限制，我们引入一个常数 \(c\)。
不管是 \(0.2N\) 还是 \(5N\)，它们都满足一个规律：运行时间和输入个数 \(N\) 成正比。我们完全可以找一个常数 \(c\)（在老电脑上 \(c\) 取 6，在超算上 \(c\) 取 1），使得 \(T(N) \le c \times N\) 恒成立。
既然 \(c\) 只是为了照顾硬件差异而存在的，那在研究算法理论时，干脆把 \(c\) 也省去！
这就诞生了大O表示法：
我们不关心具体是 \(5N\) 还是 \(0.2N\)，我们只关心它的增长趋势和 \(N\) 是一样的，直接写成：
\[T(N) = O(N) \]
原文最后一句： 通常，如果存在某个函数f使得T(N)<=cf(N)，那么对于某个常量c和任意大的N，我们定义T(N)=O(f(N)) (注：原文结尾的cN应为笔误或排版残留)
大白话推导闭环：
举个例子：
如果一个算法最坏情况要跑 \(T(N) = 2N + 10\) 步。
当 \(N > 10\) 时，我们可以肯定 \(2N + 10 < 3N\)。
这里的 \(c = 3\)，\(f(N) = N\)。因为 \(T(N) \le 3N\)，所以这个算法的复杂度就是 \(O(N)\)（线性阶）。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。