大O,你如何计算/近似它?

我是本地大学数据结构和算法课程的教授助理。我将尽我最大的努力在这里用简单的术语解释它,但请注意,这个主题需要我的学生几个月才能最终掌握。您可以在 Data Structures and Algorithms in Java 书。

没有 mechanical procedure 这可以用来得到大的。

作为一本“食谱”,获得 BigOh 从一段代码中,您首先需要认识到,您正在创建一个数学公式,以计算在给定大小的输入下执行了多少个计算步骤。

其目的很简单:从理论上比较算法,而不需要执行代码。步数越小,算法越快。

例如,假设您有这段代码:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

此函数返回数组中所有元素的和,我们希望创建一个公式来计算 computational complexity 功能:

Number_Of_Steps = f(N)

所以我们有 f(N) ,用于计算计算步骤数的函数。函数的输入是要处理的结构的大小。它意味着调用此函数,例如:

Number_Of_Steps = f(data.length)

参数 N 拿着 data.length 价值。现在我们需要函数的实际定义 f() . 这是从源代码完成的,在源代码中,每个感兴趣的行的编号从1到4。

计算bigoh的方法有很多。从这一点出发,我们假设每个不依赖于输入数据大小的句子都取一个常量。 C 数计算步骤。

我们将添加函数的单个步骤数,而局部变量声明和RETURN语句都不取决于 data 数组。

这意味着第1行和第4行中的每一步都要执行C数量的步骤,并且函数有点像这样:

f(N) = C + ??? + C

下一部分是定义 for 语句。记住,我们正在计算计算步骤的数量,这意味着 对于 语句被执行 n 时代。这和增加 C , n 时代:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

没有机械规则来计算身体的多少倍 对于 在执行时,您需要通过查看代码的作用来计算它。为了简化计算,我们忽略了 对于 语句。

为了得到真正的大目标,我们需要 Asymptotic analysis 功能。大致如下:

1. 去掉所有常量 C .
2. 从 F-() 得到 polynomium 在其 standard form .
3. 划分多项式的项,并按增长率对其进行排序。
4. 保持一个更大的当 n 方法 infinity .

我们的 F-() 有两个术语:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

带走所有的 C 常量和冗余部分:

f(N) = 1 + N ^ 1

因为最后一个学期是在 F-() 接近无穷大 limits )这是一个重要的论点, sum() 函数的bigoh为:

O(N)

有几个技巧可以解决一些棘手的问题:使用 summations 尽你所能。

例如,使用求和可以很容易地解决此代码:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

你需要问的第一件事是 foo() . 而通常是 O(1) 你得问问你的教授。 O(1) 表示(几乎,大部分)常量 C ,与大小无关 n .

这个 对于 对第一句话的陈述很棘手。当索引结束于 2 * N ,增量为2。这意味着第一个 对于 只执行 n 步骤,我们需要将计数除以2。

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

句子编号 二 因为它取决于 i . 看一下:索引i取的值是:0,2,4,6,8,…,2*n,第二个 对于 执行:n乘以第一个,n-2乘以第二个,n-4乘以第三个…到N/2级,第二级 对于 永远不会被处决。

在公式上,这意味着:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

我们又开始数了 步数 . 根据定义,每个求和都应该从一开始,以大于或等于一的数字结束。

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(我们假设 英尺() 是 O(1) 并采取 C 步骤)

我们这里有个问题:什么时候 我 取价值 N / 2 + 1 向上,内部求和以负数结束!那是不可能的,也是错误的。我们需要将总和分为两部分,作为关键点 我 拿 n/2+1 .

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

从关键时刻开始 i > N / 2 内部 对于 不会被执行,我们假设在其主体上有一个恒定的C执行复杂性。

现在可以使用一些标识规则简化求和:

1. 求和(w从1到n)(c)=n*c
2. 求和(w从1到n)(a(+/-)b)=求和(w从1到n)(a)(+/-)求和(w从1到n)(b)
3. 求和(w从1到n)(w*c)=c*求和(w从1到n)(w)(c是一个常数,独立于 w )
4. 求和(w从1到n)(w)=(n*(n+1))/2

应用代数:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

大问题是:

O(N²)

大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),因为至多我们需要查看整个列表才能找到我们的号码。大O仍然是O(N),尽管我们可能会在第一次尝试时找到我们的数字,并在循环中运行一次,因为大O描述了一个算法的上界(ω表示下界,θ表示紧界)。

当我们进入嵌套循环时:

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

这是O(n^2),因为对于外部循环(o(n))的每一次,我们都必须再次遍历整个列表,所以n的乘法留给我们n的平方。

这仅仅是表面上的擦伤,但是当你分析更复杂的算法时,涉及证明的复杂数学就开始起作用了。希望这至少能让你熟悉基础知识。

虽然知道如何为您的特定问题找出大的O时间是有用的,但是了解一些一般情况在帮助您在算法中做出决策方面会有很大的帮助。

以下是一些最常见的案例 http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

o(1)-确定数字是偶数还是奇数;使用常量大小的查找表或哈希表

o(logn)-使用二进制搜索在已排序的数组中查找项

o(n)-在未排序的列表中查找项目;添加两个n位数

O(n) ^二 )-将两个n位数乘以一个简单算法;添加两个n n矩阵;冒泡排序或插入排序

O(n) ^三 )-用简单算法乘两个神经网络矩阵

O(C) ⁿ )-使用动态编程找到旅行商问题的(精确)解决方案;使用蛮力确定两个逻辑语句是否等效

O(n)!-通过暴力搜索解决旅行推销员问题

O(n) ⁿ )-常用于代替O(N!)求渐近复杂度的简单公式

小提示: big O 符号用于表示 渐近性 复杂性(也就是说,当问题的规模扩大到无穷大时) 和 它隐藏了一个常量。

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

注意,隐藏常量很大程度上取决于实现!

此外,在某些情况下,运行时不是 大小 输入的n。以使用快速排序为例:对n个元素数组排序所需的时间不是常量,而是取决于数组的初始配置。

有不同的时间复杂性:

• 最坏的情况(通常是最容易理解的,尽管并不总是很有意义的)

• 一般情况(通常很难确定…)

• …

一个好的介绍是 算法分析导论 作者:R.Sedgewick和P.Flajolet。

正如你所说的, premature optimisation is the root of all evil ,和(如果可能) 仿形 在优化代码时应该始终使用really。它甚至可以帮助您确定算法的复杂性。

看到这里的答案,我想我们可以得出这样的结论:我们大多数人确实是通过 看 用常识来计算,而不是用 master method 就像我们在大学里被认为的那样。 我必须补充一点,就是教授也鼓励我们 认为 关于它,而不是仅仅计算它。

另外,我想补充一下 递归函数 :

假设我们有一个函数( scheme code ):

(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)

Peter 回答 your raised issues; 我在这里描述的方法实际上处理得很好。但请记住,这仍然是一个 近似 而不是一个完全正确的数学答案。这里描述的方法也是我们在大学里教的方法之一,如果我记得正确的话,它被用于比我在这个例子中使用的阶乘更高级的算法中。
当然,这一切都取决于您如何估计函数体的运行时间和递归调用的数量,但对于其他方法也是如此。

如果您的成本是一个多项式,只需保留最高阶项,不带乘数。例如。:

o((n/2+1)*(n/2))=o(n ^二 /4+n/2)=O(n) ^二 / 4)=O(n) ^二 )

这不适用于无限系列,请注意。一般情况没有单一的解决方法,但对于某些常见情况,以下不平等适用:

O(原木) n (o) n (o) n 日志 n (o) n ^二 (o) n ^K (e)(e) ⁿ (o) n !)

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

您的基本工具是决策点及其熵的概念。决策点的熵是它将给你的平均信息。例如,如果一个程序包含一个具有两个分支的决策点,那么它的熵就是每个分支的概率乘以日志的总和。 _二 那一分支的逆概率。这就是你通过执行这个决定学到的东西。

例如,一个 if 具有两个分支的语句,这两个分支同样可能具有1/2*log(2/1)+1/2*log(2/1)=1/2*1+1/2*1=1的熵。所以它的熵是1位。

假设您正在搜索一个包含n个项目的表,如n=1024。这是一个10位的问题,因为日志(1024)=10位。因此,如果你能用同样可能产生结果的if语句来搜索它,那么它应该做出10个决定。

这就是二进制搜索的结果。

假设您正在进行线性搜索。你看第一个元素,然后问它是否是你想要的元素。概率是1/1024,而不是1023/1024。该决策的熵是1/1024*对数(1024/1)+1023/1024*对数(1024/1023)=1/1024*10+1023/1024*约0=0.01位。你学得很少!第二个决定并不好。这就是线性搜索如此缓慢的原因。事实上,它是你需要学习的比特数的指数。

假设您正在进行索引。假设该表被预先排序到许多容器中,并且您使用键中的一些所有位直接索引到表条目。如果有1024个容器,则熵为1/1024*对数(1024)+1/1024*对数(1024)+…所有1024个可能的结果。这是1024个结果的1/1024*10倍,或者是一个索引操作的10位熵。这就是索引搜索快速的原因。

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

因此,基于具有大致相同可能结果的二元决策进行排序,都需要执行大约o(n log n)个步骤。如果基于索引搜索,则可以使用O(N)排序算法。

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

让我们从头开始。

首先,接受这样一个原则,即某些简单的数据操作可以在 O(1) 时间,即与输入大小无关的时间。这些C语言中的原始操作包括

1. 算术运算(如+或%)。
2. 逻辑操作(例如&&)。
3. 比较操作(例如,<=)。
4. 结构访问操作(例如数组索引,如[i]或指针fol- 使用->运算符降低)。
5. 简单的赋值,例如将值复制到变量中。
6. 调用库函数(例如scanf、printf)。

这一原理的理由需要对典型计算机的机器指令(原始步骤)进行详细研究。每一个描述的操作都可以用少量的机器指令来完成;通常只需要一个或两个指令。 因此,C中的几种语句可以在 O(1) 时间,也就是说,与输入无关的固定时间量。这些简单的包括

1. 在表达式中不涉及函数调用的赋值语句。
2. 阅读陈述。
3. 编写不需要函数调用来计算参数的语句。
4. 跳转语句break、continue、goto和return表达式,其中 表达式不包含函数调用。

在C语言中,许多for循环是通过将索引变量初始化为某个值和 在循环中每次增加该变量1。for循环结束于 指数达到了一定的极限。例如,for循环

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

使用索引变量i。它在循环和迭代中每次将i递增1 当我到达N 1时停止。

然而,目前,重点关注for循环的简单形式,其中 最终值和初始值之间的差除以索引变量的增量告诉我们循环的次数。 . 这个计数是精确的,除非有通过跳转语句退出循环的方法;在任何情况下,它都是迭代次数的上限。

例如,for循环迭代 ((n − 1) − 0)/1 = n − 1 times , 因为0是i的初始值,n 1是i达到的最高值(即当i 达到n1,循环停止,i=n1时不发生迭代),加1 在循环的每个迭代中。

在最简单的情况下,循环体中花费的时间对于每个循环体都是相同的 迭代, 我们可以用身体的大oh上限乘以 循环时间 . 严格来说,我们必须 添加O(1)次初始化 第一次比较循环索引与 限制 因为我们测试的次数比循环的次数多。然而,除非 可以执行循环零次,初始化循环和测试的时间 极限一次是一个低阶项,可以通过求和规则来降低。

现在考虑这个例子:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

我们知道 线(1) 拿 O(1) 时间。很明显,我们绕了n圈, 我们可以通过从在线找到的上限中减去下限来确定。 (1)然后加1。由于身体,第(2)行,需要O(1)时间,我们可以忽略 增加j的时间和比较j与n的时间,两者都是o(1)。 因此,线路(1)和(2)的运行时间是 n和o的乘积(1) ,这就是 O(n) .

同样,我们可以限定由线组成的外循环的运行时间。 (2)到(4),即

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

我们已经确定了线(3)和(4)的循环需要O(n)时间。 因此,我们可以忽略O(1)时间来增加I并测试 每次迭代,得出的结论是外部循环的每次迭代都需要O(n)个时间。

外部循环的初始化i=0和条件的(n+1)st测试 I<N同样需要O(1)时间,可以忽略不计。最后,我们观察到 绕外循环n次,每次迭代取0(n)次,得出 O(n^2) 运行时间。

一个更实际的例子。

如果您想根据经验而不是通过分析代码来估计代码的顺序,那么您可以使用一系列增加的n值来计算代码的时间。在对数刻度上绘制计时。如果代码是O(x^n),则值应落在坡度n的直线上。

这比仅仅研究代码有几个优势。首先,您可以看到是否处于运行时间接近其渐近顺序的范围内。此外,您可能会发现一些您认为是O(X)顺序的代码实际上是O(X^2)顺序,例如,因为在库调用中花费了时间。

基本上,90%的时间都是在分析循环。您有单、双、三个嵌套循环吗?你有O(n),O(n^2),O(n^3)运行时间。

非常少(除非你正在编写一个具有广泛基础库的平台(例如,.Net BCL,或者C++的STL),你会遇到比查看你的循环更困难的事情(for语句,而GOTO,等等)。

把算法分解成你知道的大O符号,然后通过大O运算符组合。这是我唯一知道的方法。

有关详细信息,请检查 Wikipedia page 关于这个问题。

大O符号是有用的,因为它很容易处理和隐藏不必要的复杂和细节(对于一些不必要的定义)。计算分治算法复杂性的一个好方法是树方法。假设您有一个带有中间过程的Quicksort版本,所以每次都要将数组分割成完全平衡的子数组。

现在,构建一个与您使用的所有数组对应的树。在根目录中,您有原始数组,根目录有两个子目录,它们是子数组。重复此操作,直到底部有单个元素数组。

因为我们可以在O(n)时间中找到中位数,并在O(n)时间中将数组分成两部分,所以在每个节点上完成的工作是O(k),其中k是数组的大小。树的每个级别都包含(最多)整个数组,因此每个级别的工作是O(n)(子数组的大小加起来是N,因为我们每个级别都有O(k),所以可以加起来)。因为每次我们将输入减半,所以树中只有日志(n)级别。

因此,我们可以用o(n*log(n))来限定工作量。

然而,大O隐藏了一些我们有时不能忽视的细节。考虑计算斐波那契序列

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

让我们假设A和B是Java中的大整数或者可以处理任意大数的事物。大多数人会说这是一个没有退缩的O(N)算法。原因是for循环中有n个迭代,而o(1)在循环的一侧工作。

但是斐波那契数很大,第n个斐波那契数在n中是指数级的,所以只存储它就需要n个字节的顺序。用大整数执行加法需要O(n)个工作量。所以这个过程中完成的总工作量是

1+2+3+…+n=n(n-1)/2=o(n^2)

所以这个算法是以四次方的时间运行的!

熟悉我使用的算法/数据结构和/或迭代嵌套的快速浏览分析。困难在于,当您调用一个库函数时,可能会多次调用——您通常不确定是否在某些时候不必要地调用该函数,或者它们使用的是什么实现。也许库函数应该有一个复杂度/效率度量,无论是大O还是其他度量标准,这些度量标准在文档中甚至是 IntelliSense .

我认为一般来说没什么用处,但为了完整性,还有一个 Big Omega Ω 定义了算法复杂性的下限,以及 Big Theta Θ 定义了上界和下界。

至于“你怎么计算”大O,这是 Computational complexity theory . 对于某些(许多)特殊情况,您可以使用一些简单的启发式方法(例如,将循环计数乘以嵌套循环),特别是当您只需要任何上界估计时,您不介意它是否过于悲观-我猜这可能是您的问题所在。

如果你真的想回答任何算法的问题,你能做的最好的就是应用这个理论。除了简单的“最坏情况”分析,我发现 Amortized analysis 在实践中非常有用。

对于第一种情况,执行内部循环 n-i 次,因此执行的总数是 i 从出发 0 到 n-1 (因为低于、不低于或等于) N-I . 你终于得到 n*(n + 1) / 2 如此 O(n²/2) = O(n²) .

对于第二个循环, 我 是介于 零 和 n 包含在外循环中;然后在 j 严格大于 n 这是不可能的。

除了使用主方法(或它的一个专门方法),我还通过实验测试了我的算法。这不能 证明 任何一个特定的复杂性类都可以实现,但它可以保证数学分析是适当的。为了帮助消除这种疑虑,我将代码覆盖工具与我的实验结合使用,以确保我正在练习所有的案例。

作为一个非常简单的例子,您希望对.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);

别忘了还要考虑到空间的复杂性,如果内存资源有限的话,这也会引起人们的关注。例如,您可能会听到有人想要一个常量空间算法,这基本上是一种表示算法所占用的空间量不依赖于代码中的任何因素的方法。

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

最后,大O可以用于最坏情况、最佳情况和摊销情况,通常情况下,最坏情况用于描述算法可能有多差。

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

您的算法的预期行为——非常简单——您可以期望您的算法以多快的速度处理您最可能看到的数据。

例如,如果您在列表中搜索一个值,它是O(N),但是如果您知道您看到的大多数列表都有您的值,那么您的算法的典型行为会更快。

要真正确定它,您需要能够描述“输入空间”的概率分布(如果您需要对列表进行排序,那么该列表已经排序的频率是多少?完全颠倒的频率是多少?它通常多久排序一次?)你知道这一点并不总是可行的,但有时你知道。

好问题!

如果你用的是大O型,你说的是更糟的情况(更多的是后面的意思)。另外,一般情况下有大写的theta,最好情况下有大的omega。

查看此网站,了解Big O的可爱正式定义: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n)=o(g(n))表示存在正常数c和k,因此,所有n k的0·f(n)·c g(n)。c和k的值对于函数f必须是固定的,不能依赖n。

好吧,那么现在我们所说的“最佳情况”和“最坏情况”的复杂性是什么意思呢?

这可能是通过示例最清楚地说明的。例如,如果我们使用线性搜索在排序的数组中查找一个数字,那么 最坏情况 当我们决定 搜索最后一个元素 在数组中执行的步骤与数组中的项一样多。这个 最佳情况 当我们搜索 第一要素 因为我们会在第一次检查之后完成。

所有这些的要点 形容词 -案例的复杂性在于,我们正在寻找一种方法,根据特定变量的大小来绘制一个假设程序运行到完成的时间。然而,对于许多算法,您可以争辩说,对于特定大小的输入,没有单一的时间。注意,这与函数的基本要求相矛盾,任何输入都不应该有多个输出。所以我们想出了 倍数 描述算法复杂性的函数。现在,尽管搜索大小为n的数组可能需要不同的时间,这取决于您在数组中查找的内容以及与n成比例的时间,但我们可以使用最佳情况、平均情况和最坏情况类创建算法的信息性描述。

很抱歉,这篇文章写得太差,缺少很多技术信息。但希望它能让时间复杂性类更容易思考。一旦你对这些感到满意,它就变成了一个简单的问题,通过你的程序进行分析,寻找依赖于数组大小的循环,并根据你的数据结构进行推理,什么样的输入会导致一些小的情况,什么样的输入会导致最坏的情况。

我不知道如何以编程的方式解决这个问题,但人们首先要做的是,我们在完成的操作数量中对特定模式的算法进行采样,例如4n^2+2n+1,我们有两个规则:

1. 如果我们有一个条款的总和,则保持增长率最大的条款,而忽略其他条款。
   
2. 如果我们有几个因子的乘积,常数因子就会被忽略。

如果我们简化f(x),其中f(x)是完成的操作数的公式(上面解释的4n^2+2n+1),我们得到大的o值[o(n^2),在这种情况下]。但这必须考虑到程序中的拉格朗日插值,这可能很难实现。如果真正的大O值是O(2^n),我们可能有类似O(x^n)的值,那么这个算法可能无法编程。但如果有人证明我错了,就给我密码。….

对于代码A,外部循环将执行 n+1 时间,“1”时间是指检查我是否仍然满足要求的过程。内部循环运行 n 时代, n-2 时代…因此, 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²) .

对于代码B,虽然内部循环不会介入并执行foo(),但内部循环将执行N次,这取决于外部循环的执行时间,即o(n)