大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。
但我很好奇,你是如何计算或近似你的算法的复杂性的?
大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。
但我很好奇,你是如何计算或近似你的算法的复杂性的?
当前回答
如果您希望根据经验而不是通过分析代码来估计代码的顺序,您可以插入一系列不断增加的n值,并为代码计时。在对数刻度上绘制你的时间。如果代码是O(x^n),值应该落在斜率为n的直线上。
这比只研究代码有几个优点。首先,您可以看到您是否在运行时接近其渐近顺序的范围内。此外,您可能会发现一些您认为是O(x)阶的代码实际上是O(x^2)阶的代码,例如,因为花在库调用上的时间。
其他回答
如果您希望根据经验而不是通过分析代码来估计代码的顺序,您可以插入一系列不断增加的n值,并为代码计时。在对数刻度上绘制你的时间。如果代码是O(x^n),值应该落在斜率为n的直线上。
这比只研究代码有几个优点。首先,您可以看到您是否在运行时接近其渐近顺序的范围内。此外,您可能会发现一些您认为是O(x)阶的代码实际上是O(x^2)阶的代码,例如,因为花在库调用上的时间。
我从信息的角度来考虑。任何问题都包括学习一定数量的比特。
你的基本工具是决策点及其熵的概念。一个决策点的熵是它会给你的平均信息。例如,如果一个程序包含一个有两个分支的决策点,它的熵是每个分支的概率乘以该分支的逆概率的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还是其他度量,都可以在文档或智能感知中得到。
对于代码A,外层循环将执行n+1次,“1”时间表示检查i是否仍然满足要求的过程。内循环运行n次,n-2次....因此,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²)。
对于代码B,虽然内部循环不会介入并执行foo(),但内部循环将执行n次,这取决于外部循环的执行时间,即O(n)
小提示:大O符号是用来表示渐近复杂度的(也就是说,当问题的大小增长到无穷大时),它隐藏了一个常数。
这意味着在O(n)和O(n2)的算法之间,最快的并不总是第一个算法(尽管总是存在一个值n,这样对于大小为>n的问题,第一个算法是最快的)。
注意,隐藏常数很大程度上取决于实现!
此外,在某些情况下,运行时并不是输入大小为n的确定函数。以快速排序为例:对n个元素的数组进行排序所需的时间不是一个常数,而是取决于数组的初始配置。
有不同的时间复杂度:
最坏的情况(通常是最简单的,但并不总是很有意义) 一般情况下(通常很难弄清楚…) ...
一个很好的介绍是R. Sedgewick和P. Flajolet的《算法分析导论》。
正如你所说,过早的优化是万恶之源,(如果可能的话)在优化代码时真的应该总是使用分析。它甚至可以帮助您确定算法的复杂性。