开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >大O表示法解释/证明

问大O表示法解释/证明
EN

Stack Overflow用户

提问于 2015-01-20 08:33:09

回答 2查看 573关注 0票数 1

当确定一个函数是否是另一个函数的大o时，我仍然很难理解更复杂的证明，例如(f(n) =O(g(N)。

示例：

F(n) http://upurs.us/image/63058.gif

G(n) http://upurs.us/image/63059.gif

我认识到，当n> b时，我们想要在S.Tf(N) <= C1 * g(n)条件下满足证明，我看过无数的教程，不能理解这个概念。在列出的例子中，我将如何选择常量并使用这些信息来完成证明？谢谢。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2015-01-20 09:04:33

您所要做的就是考虑f(n)和g(n)在n到infinity时的重要条款。

现在考虑一下f(n)：

和g(n)：

现在的结论是：

票数 2

EN

Stack Overflow用户

发布于 2015-01-20 09:39:37

我认为这个问题有两个部分。第一种是确定哪个函数(如果两者都有)具有更大的渐近增长。第二是证明你所决定的是正确的。

至于第一部分，我建议简单地看一下序列中最有力的术语。F和g的阶分别为2.5 (5n^2 * sqrt(n)和6n^2 * sqrt(n) )。在丢弃系数后，哪一个在n走向无穷远时增长得更快？结果表明，去掉这些系数会得到相同的精确函数(即n^2 * sqrt(n))，因此这些函数具有相等的渐近增长。这意味着我们可以证明f= O(g)和g= O(f)。

为了证明第一个，我们只需要找到一些C和k，使得对于所有n>k，我们都有C* g(n) > f(n)。我认为最容易做到这一点的方法之一就是用矛盾来证明。这就是说，假设对于所有C和k，f(n) >C* g(n)对于所有n> k，那么，在简化表达式之后，我们可以选择C和k的大值来证明这个假设是错误的。

票数 0

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/28050496

复制

相关文章

NaN和Infinity，null和undefined

javascript 编程算法

看到这个标题，大家对这4个变量应该都不陌生，但若说起他们的差别或者是举个小栗子判断结果，估计就有点晕乎乎的了。

jojo

2022/04/01

1.2K0

原 NaN和Infinity，null和u

java swift python

作者：汪娇娇日期：2016.10.10 看到这个标题，大家对这4个变量应该都不陌生，但若说起他们的差别或者是举个小栗子判断结果，估计就有点晕乎乎的了。 1、NaN和Infinity 那先来说说JavaScript的数据类型，有Number、字符串、布尔值、对象等等，而NaN和Infinity就属于Number类型。先说说它俩的差别： NaN; // NaN表示Not a Number，当无法计算结果时用NaN表示 Infinity; // Infinity表示无限大，当数值超过了JavaScript的Nu

jojo

2018/05/03

1.1K0

java中double的NAN和INFINITY

在开发中double的处理时会出现NAN（无穷小）和INFINITY（无穷大）的情况，所以我们需要在这种情况时加一下处理

余生大大

2022/10/25

1.2K0

[C] C语言中的nan和inf使用

c 语言 http 编程算法 windows

本文总结nan和inf在C语言当中的含义、产生和判定方法。 C语言当中的nan 表示not a number，等同于 #IND:indeterminate (windows) 产生：对浮点数进行了未定义的操作；

轻舞飞扬SR

2021/02/24

3.5K0

C语言中switch语句_switch在c语言中

c 语言 linux 编程算法 java

本篇文章帮大家学习c语言switch语句，包含了C语言switch语句使用方法、操作技巧、实例演示和注意事项，有一定的学习价值，大家可以用来参考。

全栈程序员站长

2022/09/27

2.7K0

ValueError: Input contains NaN, infinity or a value too large for dtype(‘float64’).

python anaconda https java

笔者在使用LogisticRegression模型进行预测时，报错 Traceback (most recent call last): File “D:/软件（学习）/Python/MachineLearing/taitannike/train.py”, line 55, in predicted_np = clf.predict(test_np) File “D:\Python\Anaconda\lib\site-packages\sklearn\linear_model\base.py”, line 281, in predict scores = self.decision_function(X) File “D:\Python\Anaconda\lib\site-packages\sklearn\linear_model\base.py”, line 257, in decision_function X = check_array(X, accept_sparse=‘csr’) File “D:\Python\Anaconda\lib\site-packages\sklearn\utils\validation.py”, line 573, in check_array allow_nan=force_all_finite == ‘allow-nan’) File “D:\Python\Anaconda\lib\site-packages\sklearn\utils\validation.py”, line 56, in _assert_all_finite raise ValueError(msg_err.format(type_err, X.dtype)) ValueError: Input contains NaN, infinity or a value too large for dtype(‘float64’). Age False

全栈程序员站长

2022/09/03

1.6K0

ValueError: Input contains NaN, infinity or a value too large for dtype(‘float64’).

从Ndom语浅谈语言中的进制

这题粗看复杂，其实不然。首先不难看出，abo、an并不是数字，所以不是加法就是乘法。因为abo出现的十分多，所以我们可以简单地假设abo是加法。接下来需要确定进制。我们知道1-10的乘方之间，出现了三个单独的词。不难得出，肯定1个是1，一个是基数的平方。除了这两个，只剩一个单独的词，那么这个词只可能是2^2=4。由此我们可以确定，Ndom语言的数字表达的基数肯定大于4且小于9。因为nif为很多长词的开头，所以nif应该是基数的平方。在题2的等式我们发现meregh乘上sas结尾的词，结果竟然还是以meregh尾！所以很明显sas就是1，于是thonith就是4。接着找，就找到了余下几个小于基数的词（于abo、an之后的较小）：ithin、meregh、thef（可能是2、3、5）。剩下的mer、nif、tondor估计就是基数的倍数了，通过观察nif abo tondor abo mer abo thonith，发现nif>tondor>mer。按照推论，mer abo ithin应该是第三小的数字——9，那么mer应该就是基数了。ithin肯定不是1、4，所以排除5、8进制可能。那么就只剩下6、7进制两种可能了。分析得mer an thef abo thonith是第4小的，即16。mer*thef+4=16⇒mer*thef=12。所以只有一种可能：Ndom语言的数字是6进制。所以mer为6，thef为2，nif是mer的平方即36，ithin是9-6=3。排除法得，meregh是5。最后还有一个tondor，通过推断tondor abo mer abo sas≥6*2+6+1=19最近的平方数是25，可以判断tondor是18。至此，我们已经推断完成所有的词。剩下就是一些小小的规则，比如表示72,并不是nif an thef，而是直接nif thef。还有就是大的数字一定会在前。所以我们就能写出：58=36+18+4也就是nif abo tondor abo thonith，而87=36*2+6*2+3即nif thef abo mer an thef abo ithin。参考答案：

KAAAsS

2022/01/13

11.3K0

为什么在Go语言中要慎用interface{}

go java 人工智能

在掘金上看到一篇从java转Go思想上的变化以及对go语言思考的文章，写的很透彻，我也推敲了一遍。这里也分享给大家，或许对将要或者已经学习golang的同学有所帮助。提示：代码块可以左右拖动哦~~

我的小碗汤

2018/08/22

1.4K0

为什么在Go语言中要慎用interface{}

void loop在c语言中什么意思,C语言中的loop是什么意思,在C语言中loop是什么意思？…[通俗易懂]

https java 网络安全

另附上goto,break, continue和return用法：=========================================== 程序中的语句通常总是按顺序方向，或按语句功能所定义的方向执行的。

全栈程序员站长

2022/08/30

2.7K0

GCC在C语言中内嵌汇编-转载

单片机 ide 汇编语言 c 语言 gcc

在内嵌汇编中，可以将C语言表达式指定为汇编指令的操作数，而且不用去管如何将C语言表达式的值读入哪个寄存器，以及如何将计算结果写回C 变量，你只要告诉程序中C语言表达式与汇编指令操作数之间的对应关系即可， GCC会自动插入代码完成必要的操作。 1、简单的内嵌汇编例：

战神伽罗

2019/07/24

2.9K0

为什么不带参数的 Math.max() 返回-Infinity

https 编程算法网络安全 github git

Math.max() 是 JS 内置的方法，可以从传入的参数中，返回最大的一个。例如：

前端小智@大迁世界

2022/06/15

1.1K0

system在c语言中_c语言system返回值

windows https java unix 网络安全

C 库函数 int system(const char *command) 把 command 指定的命令名称或程序名称传给要被命令处理器执行的主机环境，并在命令完成后返回。

全栈程序员站长

2022/09/29

1.9K0

在c语言中，数组 a[i++] 和数组 a[++i] 有区别吗？ && 在c语言中，数组 a[0]++; 又是什么意思？

b = a++; 　　　//先计算表达式的值，即先把a赋值给了b；然后a再自加1。 b = ++a；　　 //先a自加1后；然后把a自加后得到的赋值给b。

黑泽君

2018/10/11

3.4K0

JavaScript面向对象编程指南第一、二章知识点整理

java 面向对象编程存储

第一章、面向对象的JavaScript 面向对象程序设计（OOP,Object -Oriented Programming）中最常用到的概念：对象：是指"事物"在程序设计语言中的表现形式。这里的"事物"可以是任何东西。例如，对于猫这种常见对象来说，我们可以看到它们具有某些明确的特征（如颜色、名字、体型等），能执行某些动作（如喵喵叫、睡觉等）。在OOP语义中，这些对象特征都叫做属性，而那些动作则被称为方法。类：在面向对象编程中，类（class）是对象（object）的模板，定义了同一组对象（又称

小胖

2018/06/27

4050

0.1+0.2=0.30000000000000004问题的探究

java 存储人工智能

首先声明这不是bug，原因在与十进制到二进制的转换导致的精度问题！其次这几乎出现在很多的编程语言中：C/C++,Java,Javascript中，准确的说：“使用了IEEE 754浮点数格式”来存储浮点类型(float 32,double 64)的任何编程语言都有这个问题！

mmzhou

2018/08/01

6990

c/c++ -nan(ind) NAN

nan -- 表示出错，“不是一个数” not a number 的缩写。按 IEEE 754 国际标准，当运算中出现无效数据时，给出 NaN. 许多情况会出现，例如 0 除 0，负数开平方，...

acoolgiser

2019/01/17

3.5K0

C语学习之 getchar() putchar()

// 使用getchar() 和puchar()演示 #include "stdafx.h" int main(int argc, char* argv[]) { char a,b,c,d,e; printf("请输入5个字符：\n"); a=getchar(); b=getchar(); c=getchar(); d=getchar(); e=getchar(); putchar(a); putchar(b); putchar(c); putchar(d); putchar(e)

明明如月学长

2021/08/27

1.7K0

lodash源码分析之NaN不是NaN

暗恋之纯粹，在于不求结果，完全把自己锁闭在一个单向的关系里面。 ——梁文道《暗恋到偷窥》本文为读 lodash 源码的第五篇，后续文章会更新到这个仓库中，欢迎 star：pocket-lodash gitbook也会同步仓库的更新，gitbook地址：pocket-lodash 本篇分析的是 eq 函数。作用与用法 eq 函数用来比较两个值是否相等。遵循的是 SameValueZero 规范。 var obj1 = {test: 1} var obj2 = {test: 1} var obj3 =

对角另一面

2018/03/30

1.9K0

lodash源码分析之NaN不是NaN

本文为读 lodash 源码的第五篇，后续文章会更新到这个仓库中，欢迎 star：pocket-lodash

对角另一面

2018/01/17

1.8K0

原三、基本概念

作者：汪娇娇时间：2017年11月4日一、语法 1、区分大小写 2、标识符指变量、函数、属性的名字，采用驼峰大小写格式。 3、注释单行：// 多行：/* */ 4、严格模式 "use strict" 5、语句以一个分号结尾，代码块用{}包起来。二、关键字和保留字关键字有指定用途； break do instanceof typeof case else new var catch finally return void continue for switch whil

jojo

2018/05/03

9460

相似问题

C语言中带有NAN、INFINITY和-INFINITY的冒泡排序

113

java NaN和-infinity

215

为什么我的代码返回NAN和Infinity？

16

为什么Math.pow(1，Infinity)返回NaN？

42

禁用Infinity和NaN异常

11

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例