大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。
但我很好奇,你是如何计算或近似你的算法的复杂性的?
大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。
但我很好奇,你是如何计算或近似你的算法的复杂性的?
当前回答
基本上90%的情况下都是分析循环。你有单、双、三重嵌套循环吗?你有O(n) O(n²)O(n³)的运行时间。
很少(除非你正在编写一个具有广泛基库的平台(例如,.NET BCL或c++的STL),你会遇到比查看循环(for语句,while, goto等…)更困难的事情。
其他回答
对于第一种情况,内部循环执行了n-i次,因此执行的总次数是i从0到n-1(因为小于,而不是小于或等于)的和。你得到最后n * (n + 1) / 2,所以O (n²/ 2)= O (n²)。
对于第二个循环,i在0到n之间。然后,当j严格大于n时执行内循环,这是不可能的。
熟悉我使用的算法/数据结构和/或快速分析迭代嵌套。难点在于,当您调用一个库函数时,可能会多次调用—您常常不确定是否在不必要的时候调用了函数,或者它们正在使用什么实现。也许库函数应该有一个复杂度/效率度量,无论是大O还是其他度量,都可以在文档或智能感知中得到。
我从信息的角度来考虑。任何问题都包括学习一定数量的比特。
你的基本工具是决策点及其熵的概念。一个决策点的熵是它会给你的平均信息。例如,如果一个程序包含一个有两个分支的决策点,它的熵是每个分支的概率乘以该分支的逆概率的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)排序算法是可行的。
我发现几乎所有的算法性能问题都可以用这种方式来看待。
我认为,一般来说用处不大,但为了完整起见,还有一个Big Omega Ω,它定义了算法复杂度的下界,还有一个Big Theta Θ,它同时定义了上界和下界。
虽然知道如何计算出特定问题的大O时间是有用的,但了解一些一般情况可以在很大程度上帮助您在算法中做出决策。
以下是一些最常见的案例,摘自http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:
O(1) -确定一个数字是偶数还是奇数;使用常量大小的查找表或哈希表
O(logn) -用二分搜索在排序数组中查找一个项
O(n) -在未排序的列表中查找一个项;两个n位数相加
O(n2) -用一个简单的算法乘以两个n位数字;添加两个n×n矩阵;冒泡排序或插入排序
O(n3) -用简单的算法乘以两个n×n矩阵
O(cn) -使用动态规划找到旅行商问题的(精确)解;使用蛮力判断两个逻辑语句是否等效
O(n!) -通过暴力搜索解决旅行推销员问题
O(nn) -通常用来代替O(n!)来推导更简单的渐近复杂度公式