gpt4 book ai didi

algorithm - 大O,您如何计算/近似?

转载 作者:太空宇宙 更新时间:2023-11-04 11:44:47 26 4
gpt4 key购买 nike

大多数拥有CS学位的人当然会知道Big O stands for是什么。
它可以帮助我们评估算法的可扩展性。

但是我很好奇,您如何计算或估算算法的复杂性?

最佳答案

我会尽力在这里简单地解释它,但要注意,这个主题需要我的学生花几个月的时间才能最终掌握。您可以在Data Structures and Algorithms in Java书的第2章中找到更多信息。



没有mechanical procedure可用于获取BigOh。

作为“食谱”,要从一段代码中获得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语句的值。请记住,我们正在计算计算步骤的数量,这意味着 for语句的主体被执行 N次。这与添加 CN次相同:

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


没有机械规则来计算 for的主体执行了多少次,您需要通过查看代码的作用来对其进行计数。为了简化计算,我们忽略了 for语句的变量初始化,条件和增量部分。

要获取实际的BigOh,我们需要函数的 Asymptotic analysis。大致是这样完成的:


带走所有常量 C
f()获取其 standard form中的 polynomium
将多项式的项除以增长率。
保持当 N接近 infinity时会变大的那个。


我们的 f()有两个术语:

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


除去所有 C常量和冗余部分:

f(N) = 1 + N ^ 1


由于最后一项是当 f()接近无穷大时考虑的项(请考虑 limits),因此这是BigOh参数,而 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无关。

关于第一句的 for语句很棘手。当索引以 2 * N结尾时,增量增加2。这意味着第一个 for仅执行 N个步骤,我们需要将计数除以二。

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,第二个 for被执行:第一个N倍,第二个N-2, N-4第三个...直到N / 2阶段,第二个 for永远不会执行。

在公式上,这意味着:

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


同样,我们正在计算步骤数。并且根据定义,每次求和应始终始于一个,并以大于或等于1的数字结束。

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


(我们假设 foo()O(1)并采取 C步骤。)

我们这里有一个问题:当 i向上取值 N / 2 + 1时,内部求和运算将以负数结束!那是不可能的,也是错误的。我们需要将总和一分为二,成为 iN / 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,内部的 for将不会执行,因此我们假设C主体上的C执行复杂度恒定。

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


求和(w从1到N)(C)= N * C
求和(w从1到N)(A(+/-)B)=求和(w从1到N)(A)(+/-)求和(w从1到N)(B)
求和(w从1到N)(w * C)= C *求和(w从1到N)(w)(C是一个常数,独立于 w
求和(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


BigOh是:

O(N²)

关于algorithm - 大O,您如何计算/近似?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42451211/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com