大多数拥有CS学位的人一定会知道Big O代表什么。
它可以帮助我们评估算法的效率(效率)，如果我们知道要解决的问题属于哪一类，则可以找出是否仍有可能榨取少量的额外性能。1

但是我很好奇，我们如何计算或者估算算法的复杂性？

1，但是正如他们所说，不要过度使用，过早的优化是万恶之源，而没有正当理由的优化也应该得到这个名字。

解决方案

回答

熟悉我使用的算法/数据结构和/或者快速浏览迭代嵌套分析。困难在于调用库函数时(可能多次)，我们常常不确定是否有时会不必要地调用该函数或者它们正在使用什么实现。也许库函数应该具有复杂性/效率度量，无论是Big O还是其他度量标准，都可以在文档中找到，甚至可以在IntelliSense中找到。

回答

将算法分解成我们知道大O表示法的部分，然后通过大O运算符进行组合。那是我所知道的唯一方法。

有关更多信息，请查看有关该主题的Wikipedia页面。

回答

大O给出了算法时间复杂度的上限。它通常与处理数据集(列表)结合使用，但可以在其他地方使用。

有关如何在C代码中使用它的一些示例。

假设我们有一个n个元素的数组

int array[n];

如果我们想访问数组的第一个元素，则为O(1)，因为数组的大小无关紧要，获取第一个元素总是需要相同的恒定时间。

x = array[0];

如果我们想在列表中找到一个数字：

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

这将是O(n)，因为至多我们将不得不遍历整个列表以找到我们的数字。尽管Big-O仍然是O(n)，尽管我们可能会第一次尝试找到我们的数字并循环运行一次，因为Big-O描述了算法的上限(omega代表下限，而theta代表紧密边界) 。

当我们进入嵌套循环时：

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

这是O(n ^ 2)，因为对于外循环(O(n))的每次通过，我们都必须再次遍历整个列表，因此n的乘积将n平方。

这勉强可以触及表面，但是当我们要分析更复杂的算法时，涉及证明的复杂数学就会发挥作用。希望这至少使我们熟悉基础知识。

回答

在这里看到答案，我认为我们可以得出结论，我们大多数人确实确实通过查看算法并使用常识而不是使用例如我们在大学时所考虑的主方法来计算算法来近似算法的阶数。
话虽如此，我必须补充一点，即使是教授也鼓励我们(以后)实际考虑而不是仅仅进行计算。

我也想补充一下递归函数的用法：

假设我们有一个类似于(方案代码)的函数：

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

递归计算给定数字的阶乘。

第一步是尝试仅在这种情况下确定函数主体的性能特征，主体上没有做任何特别的事情，只是一个乘法(或者返回值1)。

因此，对于身体的性能为：O(1)(恒定)。

下一步尝试确定递归调用的数量。在这种情况下，我们有n-1个递归调用。

因此，递归调用的性能为：O(n-1)(阶数为n，因为我们丢弃了无关紧要的部分)。

然后将这两个放在一起，就可以得到整个递归函数的性能：

1 *(n-1)= O(n)

彼得，回答我们提出的问题；我在这里描述的方法实际上可以很好地解决这个问题。但是请记住，这仍然是一个近似值，而不是一个完整的数学正确答案。这里描述的方法也是我们在大学里教过的方法之一，如果我没记错的话，它用于比本示例中使用的阶乘更高级的算法。
当然，这完全取决于我们可以对函数主体的运行时间和递归调用的数量进行估算的能力，但是其他方法也是如此。

回答

大O表示法很有用，因为它易于使用并且隐藏了不必要的复杂性和细节(对于不必要的一些定义)。树法是解决分而治之算法复杂性的一种不错的方法。假设我们有一个带有中值过程的quicksort版本，因此每次都将数组拆分为完全平衡的子数组。

现在构建一个与我们使用的所有阵列相对应的树。在根目录下，我们拥有原始数组，在根目录下有两个子数组，它们是子数组。重复此过程，直到底部有单个元素数组。

由于我们可以找到O(n)时间的中位数，并在O(n)时间中将数组分为两部分，因此每个节点的工作量为O(k)，其中k是数组的大小。树的每个级别最多包含整个数组，因此每个级别的工作量为O(n)(子数组的大小总计为n，并且由于每个级别有O(k)，因此我们可以将其相加) 。自从我们每次将输入减半后，树中只有log(n)级别。

因此，我们可以通过O(n * log(n))来限制工作量。

但是，Big O隐藏了一些有时我们无法忽略的细节。考虑使用以下方法计算斐波那契数列

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

并假设a和b是Java中的BigIntegers或者可以处理任意大数的东西。大多数人会说这是一种O(n)算法，不会退缩。原因是在for循环中有n次迭代，而O(1)在循环中起作用。

但是斐波那契数很大，第n个斐波那契数在n中是指数的，因此仅存储它就需要n个字节的顺序。用大整数执行加法将需要O(n)的工作量。因此，此过程中完成的总工作量为

1 + 2 + 3 + ... + n = n(n-1)/ 2 = O(n ^ 2)

因此，该算法运行在四基时间！

回答

基本上，90％的时间都收获的东西只是分析循环。我们有单，双，三重嵌套循环吗？我们有O(n)，O(n ^ 2)，O(n ^ 3)运行时间。

极少数情况下(除非我们正在编写带有扩展基础库的平台(例如.NET BCL或者C ++的STL)，否则我们会遇到比仅查看循环(对于语句，语句，goto，等等...)

回答

小提醒："大O"符号用于表示渐近复杂度(即，当问题的大小增长到无穷大时)，并且它隐藏了一个常数。

这意味着在O(n)中的算法与O(n2)中的算法之间，最快的并不总是第一个(尽管总存在n值，因此对于大小大于n的问题，第一个算法是最快的)。

注意，隐藏常量在很大程度上取决于实现！

同样，在某些情况下，运行时不是输入大小n的确定性函数。以使用快速排序的排序为例：对n个元素的数组进行排序所需的时间不是常数，而是取决于数组的起始配置。

时间复杂度不同：

• 最坏的情况(通常最简单，尽管并不总是很有意义)
• 一般情况(通常很难弄清楚...)
• ...

R. Sedgewick和P. Flajolet撰写的《算法分析入门》就是很好的介绍。

正如我们所说的，"过早的优化是万恶之源"，(如果可能的话)在优化代码时应始终使用概要分析。它甚至可以确定算法的复杂性。

回答

除了使用master方法(或者其专业之一)之外，我还通过实验测试了我的算法。这不能证明可以实现任何特定的复杂性类，但是可以保证数学分析是适当的。为了保证这种安全，我将代码覆盖率工具与实验结合使用，以确保我能正确执行所有案例。

举一个非常简单的例子，我们想对.NET框架的列表排序速度进行完整性检查。我们可以编写类似以下内容的内容，然后在Excel中分析结果以确保它们不超过n * log(n)曲线。

在此示例中，我测量了比较的数量，但是检查每种样本大小所需的实际时间也是谨慎的。但是，然后我们必须更加小心，仅在测量算法而不包括测试基础结构中的工件。

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}

// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

回答

虽然知道如何计算出解决特定问题的时间是很有用的，但了解一些一般情况对于在算法中做出决策可能会大有帮助。

以下是一些最常见的情况，摘自http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions：

O(1)确定一个数字是偶数还是奇数；使用恒定大小的查找表或者哈希表

O(logn)通过二分查找在排序数组中查找项目

O(n)在未排序的列表中查找项目；加两个n位数字

O(n2)通过一个简单的算法将两个n位数字相乘；加两个nn矩阵;气泡排序或者插入排序

O(n3)通过简单算法乘以两个nn矩阵

O(cn)使用动态规划找到旅行商问题的(精确)解决方案；使用蛮力确定两个逻辑语句是否等效

O(n！)通过蛮力搜索解决旅行商问题

通常用O(nn)代替O(n！)得出渐近复杂度的更简单公式

回答

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

回答

不要忘记也要考虑空间复杂性，如果内存资源有限，这也可能引起人们的关注。因此，例如，我们可能听到有人想要一个恒定空间算法，这基本上是一种说法，即算法占用的空间量不依赖于代码内的任何因素。

有时，复杂性可能来自于所谓的调用次数，循环执行的频率，内存分配的频率等等，这是回答此问题的另一部分。

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

回答

如果我们想凭经验估计代码的顺序而不是通过分析代码，则可以坚持使用一系列递增的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 *大约0 =大约0.01位。我们学到的很少！第二个决定并不更好。这就是线性搜索如此缓慢的原因。实际上，它是我们需要学习的位数的指数。

假设我们正在建立索引。假设该表已预先分类为很多bin，并且我们使用键中的所有位中的某些位来直接索引该表项。如果有1024个bin，则对于所有1024个可能的结果，熵为1/1024 * log(1024)+ 1/1024 * log(1024)+ ...这是1/1024 * 10乘以1024个结果，或者该索引操作的10位熵。这就是为什么索引搜索速度快的原因。

现在考虑排序。我们有N个项目，并且有一个列表。对于每个项目，我们必须搜索该项目在列表中的位置，然后将其添加到列表中。因此，排序大约需要基础搜索步骤数的N倍。

因此，基于具有大致相同可能性结果的二元决策进行的排序全都需要O(N log N)个步骤。如果O(N)排序算法基于索引搜索，则它是可能的。

我发现几乎所有算法性能问题都可以通过这种方式解决。

回答

通常被忽略的是算法的预期行为。它不会改变算法的Big-O，但确实与"过早优化....."语句有关。

算法的预期行为-非常笨拙-可以预期算法在最有可能看到的数据上运行的速度。

例如，如果我们要在列表中搜索值，则为O(n)，但是如果我们知道大多数列表中都预先包含了值，则算法的典型行为会更快。

要真正确定下来，我们需要能够描述"输入空间"的概率分布(如果我们需要对列表进行排序，那么该列表已被排序的频率是多少？完全颠倒的频率是多少？多数情况下它是经过排序的吗？)我们知道这一点并不总是可行的，但有时我们确实知道。

回答

关于"如何计算" Big O，这是计算复杂性理论的一部分。对于某些(许多)特殊情况，我们可能可以使用一些简单的启发式方法(例如，对嵌套循环乘以循环计数)，特别是。当我们想要的只是任何上限估计时，并且我们不介意它是否过于悲观，我想这可能就是我们所要解决的问题。

如果我们真的想回答任何算法的问题，那么我们最好的方法就是运用理论。除了简单的"最坏情况"分析，我发现摊销分析在实践中非常有用。