我从信息的角度来考虑。任何问题都包括学习一定数量的比特。

你的基本工具是决策点及其熵的概念。一个决策点的熵是它会给你的平均信息。例如，如果一个程序包含一个有两个分支的决策点，它的熵是每个分支的概率乘以该分支的逆概率的log2的和。这就是你从执行决策中学到的东西。

例如，一个if语句有两个分支，都是等可能的，其熵为1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1。所以它的熵是1比特。

假设您正在搜索一个包含N个条目的表，例如N=1024。这是一个10位问题，因为log(1024) = 10位。所以如果你可以用if语句搜索结果的可能性相等，它应该需要10个决定。

这就是二分搜索的结果。

假设你在做线性搜索。您查看第一个元素并询问它是否是您想要的元素。是的概率是1/1024，不是的概率是1023/1024。该决策的熵为1/1024*log(1024/1) + 1023/1024 *log(1024/1023) = 1/1024* 10 + 1023/1024 * about 0 =约0.01 bit。你学得太少了!第二个决定也好不到哪里去。这就是为什么线性搜索这么慢。事实上，你需要学习的比特数是指数级的。

假设你在做索引。假设表被预先排序到许多箱子中，并且您使用键中的所有位中的一些位直接索引到表项。如果有1024个箱子，熵为1/1024 * log(1024) + 1/1024 * log(1024) +…对于所有1024个可能的结果。这是1/1024 * 10乘以1024个结果，或者对一个索引操作来说是10比特的熵。这就是为什么索引搜索是快速的。

现在想想排序。你有N个项目，你有一个列表。对于每个项目，您必须搜索项目在列表中的位置，然后将其添加到列表中。排序大约需要N倍于底层搜索的步数。

基于二元决策的排序结果都是等概率的都需要O(N log N)步。基于索引搜索的O(N)排序算法是可行的。

我发现几乎所有的算法性能问题都可以用这种方式来看待。

好问题!

免责声明:这个答案包含虚假陈述，见下面的评论。

如果您正在使用大O，那么您正在谈论的是最坏的情况(后面将详细介绍它的含义)。此外，在平均情况下有大写的theta，在最佳情况下有大的omega。

你可以在这个网站上找到大O的正式定义:https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n))表示存在正常数c和k，使得当n≥k时0≤f(n)≤cg(n)。对于函数f, c和k的值必须是固定的，且不依赖于n。

好的，那么我们所说的"最佳情况"和"最坏情况"是什么意思呢?

这一点可以通过例子得到最清楚的说明。例如，如果我们使用线性搜索在一个排序数组中查找一个数字，那么最坏的情况是我们决定搜索数组的最后一个元素，因为这将花费与数组中有多少项一样多的步骤。最好的情况是当我们搜索第一个元素时，因为我们将在第一次检查之后完成。

The point of all these adjective-case complexities is that we're looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm's complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you're looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.

抱歉，这是如此糟糕的写作和缺乏太多的技术信息。但希望这能让时间复杂度类更容易理解。一旦你熟悉了这些，你就可以很简单地解析你的程序，寻找像for-loops这样依赖于数组大小的东西，并根据你的数据结构推理什么样的输入会导致简单的情况，什么样的输入会导致最坏的情况。

基本上90%的情况下都是分析循环。你有单、双、三重嵌套循环吗?你有O(n) O(n²)O(n³)的运行时间。

很少(除非你正在编写一个具有广泛基库的平台(例如，.NET BCL或c++的STL)，你会遇到比查看循环(for语句，while, goto等…)更困难的事情。

经常被忽视的是算法的预期行为。它不会改变你的算法的大o，但它确实与“过早优化.. ..”的声明有关

你的算法的预期行为是——非常简单——你期望你的算法在你最有可能看到的数据上工作的速度有多快。

例如，如果你在一个列表中搜索一个值，它是O(n)，但如果你知道你看到的大多数列表都有你的值在前面，你的算法的典型行为会更快。

为了真正确定它，你需要能够描述你的“输入空间”的概率分布(如果你需要对一个列表排序，这个列表已经被排序的频率是多少?有多少次是完全相反的?多长时间进行一次排序?)这并不总是可行的，但有时你知道。

我认为，一般来说用处不大，但为了完整起见，还有一个Big Omega Ω，它定义了算法复杂度的下界，还有一个Big Theta Θ，它同时定义了上界和下界。

不要忘记考虑空间的复杂性，如果内存资源有限，这也是一个值得关注的问题。例如，你可能听到有人想要一个常数空间算法，这基本上是说算法所占用的空间量不依赖于代码中的任何因素。

有时，复杂性可能来自于某个东西被调用了多少次，循环执行的频率，内存分配的频率，等等，这是回答这个问题的另一部分。

最后，大O可以用于最坏情况、最佳情况和摊销情况，其中通常用最坏情况来描述算法可能有多糟糕。