- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
大多数拥有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
}
Number_Of_Steps = f(N)
f(N)
,该函数可以计算计算步骤的数量。函数的输入是要处理的结构的大小。这意味着将调用该函数,例如:
Number_Of_Steps = f(data.length)
N
采用
data.length
值。现在我们需要函数
f()
的实际定义。这是从源代码完成的,其中每个有趣的行从1到4编号。
C
个计算步骤。
data
数组的大小。
f(N) = C + ??? + C
for
语句的值。请记住,我们正在计算计算步骤的数量,这意味着
for
语句的主体被执行
N
次。这与添加
C
,
N
次相同:
f(N) = C + (C + C + ... + C) + C = C + N * C + C
for
的主体执行了多少次,您需要通过查看代码的作用来对其进行计数。为了简化计算,我们忽略了
for
语句的变量初始化,条件和增量部分。
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)
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 = ???)( ) )
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
时,内部求和运算将以负数结束!那是不可能的,也是错误的。我们需要将总和一分为二,成为
i
取
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
,内部的
for
将不会执行,因此我们假设C主体上的C执行复杂度恒定。
w
)
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²)
关于algorithm - 大O,您如何计算/近似?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54242200/
我在一本书(Interview Question)中读到这个问题,想在这里详细讨论这个问题。请点亮它。 问题如下:- 隐私和匿名化 马萨诸塞州集团保险委员会早在 1990 年代中期就有一个绝妙的主意
我最近接受了一次面试,面试官给了我一些伪代码并提出了相关问题。不幸的是,由于准备不足,我无法回答他的问题。由于时间关系,我无法向他请教该问题的解决方案。如果有人可以指导我并帮助我理解问题,以便我可以改
这是我的代码 public int getDist(Node root, int value) { if (root == null && value !=0) return
就效率而言,Strassen 算法应该停止递归并应用乘法的最佳交叉点是多少? 我知道这与具体的实现和硬件密切相关,但对于一般情况应该有某种指南或某人的一些实验结果。 在网上搜索了一下,问了一些他们认为
我想学习一些关于分布式算法的知识,所以我正在寻找任何书籍推荐。我对理论书籍更感兴趣,因为实现只是个人喜好问题(我可能会使用 erlang(或 c#))。但另一方面,我不想对算法进行原始的数学分析。只是
我想知道你们中有多少人实现了计算机科学的“ classical algorithms ”,例如 Dijkstra's algorithm或现实世界中的数据结构(例如二叉搜索树),而不是学术项目? 当有
我正在解决旧编程竞赛中的一些示例问题。在这个问题中,我们得到了我们有多少调酒师以及他们知道哪些食谱的信息。制作每杯鸡尾酒需要 1 分钟,我们需要使用所有调酒师计算是否可以在 5 分钟内完成订单。 解决
关闭。这个问题是opinion-based .它目前不接受答案。 想要改进这个问题? 更新问题,以便 editing this post 可以用事实和引用来回答它. 关闭 8 年前。 Improve
我开始学习 Nodejs,但我被困在中间的某个地方。我从 npm 安装了一个新库,它是 express -jwt ,它在运行后显示某种错误。附上代码和错误日志,请帮助我! const jwt = re
我有一个证书,其中签名算法显示“sha256rsa”,但指纹算法显示“sha1”。我的证书 SHA1/SHA2 的标识是什么? 谢谢! 最佳答案 TL;TR:签名和指纹是完全不同的东西。对于证书的强度
我目前在我的大学学习数据结构类(class),并且在之前的类(class)中做过一些算法分析,但这是我在之前的类(class)中遇到的最困难的部分。我们现在将在我的数据结构类(class)中学习算法分
有一个由 N 个 1x1 方格组成的区域,并且该区域的所有部分都是相连的(没有任何方格无法到达的方格)。 下面是一些面积的例子。 我想在这个区域中选择一些方块,并且两个相邻的方块不能一起选择(对角接触
我有一些多边形形状的点列表,我想将其包含在我页面上的 Google map 中。 我已经从原始数据中删除了尽可能多的不必要的多边形,现在我剩下大约 12 个,但它们非常详细以至于导致了问题。现在我的文
我目前正在实现 Marching Squares用于计算等高线曲线,我对此处提到的位移位的使用有疑问 Compose the 4 bits at the corners of the cell to
我正在尝试针对给定算法的约束满足问题实现此递归回溯函数: function BACKTRACKING-SEARCH(csp) returns solution/failure return R
是否有包含反函数的库? 作为项目的一部分,我目前正在研究测向算法。我正在使用巴特利特相关性。在 Bartlett 相关性中,我需要将已经是 3 次矩阵乘法(包括 Hermitian 转置)的分子除以作
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 8 年前。 Improve
问题的链接是UVA - 1394 : And There Was One . 朴素的算法是扫描整个数组并在每次迭代中标记第 k 个元素并在最后停止:这需要 O(n^2) 时间。 我搜索了一种替代算法并
COM 中创建 GUID 的函数 (CoCreateGUID) 使用“分散唯一性算法”,但我的问题是,它是什么? 谁能解释一下? 最佳答案 一种生成 ID 的方法,该 ID 具有一定的唯一性保证,而不
在做一个项目时我遇到了这个问题,我将在这个问题的实际领域之外重新措辞(我想我可以谈论烟花的口径和形状,但这会使理解更加复杂).我正在寻找一种(可能是近似的)算法来解决它。 我有 n 个不同大小的容器,
我是一名优秀的程序员,十分优秀!