腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >如何计算程序的最坏情况(大O)

问如何计算程序的最坏情况(大O)
EN

Stack Overflow用户

提问于 2013-05-31 23:46:06

回答 1查看 181关注 0票数 1

请原谅我故意说的话

下面是一个小程序节选：

for i=1 to n
  j= 0;
  while(j<=n);
  j=j+1;

如果我必须找到这段代码的复杂性(Big)：

我将首先计算内循环将执行多少次，在本例中是n+1次数，因为从1到n是n次，而且由于j是0，所以它会添加到while循环中。因此，在时间循环的总n+1次数中。

外部for循环将执行的次数为n次，因为从1到n，总计数为n。因此，总计为n+1+n是2n+1。

舍弃所有常量，它是大O(n)。

这是正确的吗？我找到这个例子的网页上说，外部循环将运行n(n+1)/2时间。我不明白这点。请帮帮我！

algorithm

time-complexity

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-06-01 00:36:58

不是的。对于i获取的每个值(其中有n )，您可以运行while (内部)循环n+1 times (j=0、j=1、...j=n)。

因此，执行行j=j+1的总次数是n*(n+1)，它位于O(n^2)中。

票数 2

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

原文链接：

https://stackoverflow.com/questions/16870389

复制

全局作用域、函数作用域、块级作用域的理解

编程算法 ecmascript

ES6中新增的概念，在ES5中是没有的，ES5中没有？没有的时候我们代码也写的好好的，现在新增的概念，我不用不行吗？来，拋一个典型的问题出来，你就明白块级作用域出现的重要性了。

yuezhongbao

2019/02/26

3.2K0

作用域与作用域链

编程算法

通常来说，一段程序代码中所用到的名字并不总是有效或可用的，而限定这个名字的可用性的代码范围就是这个名字的作用域scope。当一个方法或成员被声明，他就拥有当前的执行上下文context环境。在有具体值的context中，表达式是可见也都能够被引用。如果一个变量或者其他表达式不在当前的作用域，则将无法使用。作用域也可以根据代码层次分层，以便子作用域可以访问父作用域，通常是指沿着链式的作用域链查找，而不能从父作用域引用子作用域中的变量和引用。

WindRunnerMax

2020/08/27

2K0

java作用域-什么是JavaScript作用域、作用域链？

编程算法 java ecmascript

作用域、作用域链也是面试中出镜率很高的问题之一java作用域java作用域，同时也是中最重要的基础概念之一。

宜轩

2022/12/29

2K0

作用域和作用域链的简单理解

go 编程算法

javascript采用的静态作用域，也可以称为词法作用域，意思是说作用域是在定义的时候就创建了，而不是运行的时候。此话对于初学者很不好理解，看看下面这个例子：

ZEHAN

2020/09/23

8510

JavaScript中的作用域和作用域链

javascript

作用域是在运行时代码中的某些特定部分中变量，函数和对象的可访问性。换句话说，作用域决定了代码区块中变量和其他资源的可见性。可能这两句话并不好理解，我们先来看个例子：

刘亦枫

2020/03/19

2.3K0

Rust中的作用域及作用域的规则

rust 编程算法 ide c++

所有权是 Rust 最独特的特性，它使 Rust 能够在不需要 GC 的情况下保证内存安全。在本章中，我们将讨论所有权以及几个相关特性：借用/切片，以及 Rust 如何在内存中布局数据。

端碗吹水

2022/06/02

4K1

作用域及作用域链的解释说明

编程算法

javascript中作用域是指变量与函数可访问的范围。作用域分为两类，一种是全局作用域，一种是局部作用域。全局变量拥有全局作用域，在JavaScript代码中的任何地方都有定义。局部变量是在函数体内声明而且只作用在函数体内部以及该函数体的子函数的变量。下面我们对全局作用域和局部作用域来做一个深入的理解。

OECOM

2020/07/02

1.2K0

静态作用域和动态作用域

编程算法 c++serverless

所谓作用域规则就是程序解析名字的方法。如果一个变量的名称不在当前作用域内，则这样的变量称为 unbound variable，例如有一个函数 (lambda () (+ a a))，a 就是一个 unbound variable，在当前作用域内我们无法找到这个变量。那么调用这个函数的求值结果是什么呢？显然要根据 context 来确定，对于 unbound variables 的解析，从解析的时机来划分，有两种规则，一种是「静态作用域」（Static Scope）也被称为「词法作用域」（Lexical Scope），另一种是「动态作用域」（Dynamic Scope）1。

zhiruili

2021/08/10

2.2K0

JS作用域和作用域链

编程算法 javascript

全局变量的作用域是全局性的，即在JavaScript代码中，该全局变量处处都有定义。

前端_AWhile

2019/08/29

4.3K0

作用域、执行环境、作用域链

编程算法 javascript

作用域，之前有介绍过，JavaScript无块级作用域，只有函数作用域，简单点说就是JavaScript的作用域就是函数作用域。因为有函数作用域，所以我们有全局作用域和局部作用域的说法。

wade

2020/04/23

1.6K0

JavaScript作用域及作用域链

编程算法 javascript

作用域作用域规定了如何查找变量，也就是确定当前执行代码对变量的访问权限。 JavaScript 采用词法作用域(lexical scoping)，也就是静态作用域。因为 JavaScript 采用的是词法作用域，函数的作用域在函数定义的时候就决定了。而与词法作用域相对的是动态作用域，函数的作用域是在函数调用的时候才决定的。

青梅煮码

2023/03/02

1.6K0

JavaScript 作用域和作用域链

编程算法 javascript

作用域就是变量与函数的可访问范围。在JavaScript中，变量的作用域有全局作用域和局部作用域两种。

零式的天空

2022/03/02

1.8K0

函数作用域和块作用域

javascript 编程算法

正如上一章讨论，作用域包含了一系列的“气泡”，每一个都可以作为容器，其中包含了标识符（变量、函数）的定义，这些气泡互相嵌套并且整齐地排列成蜂窝型，排列的结构是在写代码时定义的。

Karl Du

2020/10/23

2.5K0

java作用域-javaScript预编译、作用域，作用域链详解

go 编程算法打包存储

ES5中只分为全局作用域和函数作用域java作用域，也就是说for,if,while等语句是不会创建作用域的。ES6(let,const)除外。

宜轩

2022/12/29

1.5K0

四、作用域与作用域链

编程算法 javascript

作用域与作用域链本应该是一个非常简单的概念。可是在近两年多的留言中，我发现这些概念反而成为了大多数人想不明白的点，而感到困惑的原因在于，别的文章里，常常会提到词法作用域，词法分析等概念，到底是什么东西？好像跟我说的有一点不一样，但又不知道哪里不对？

用户6901603

2020/07/25

1.6K0

JS作用域与作用域链

前端 javascript 作用域

作用域就是一个独立的地盘，让变量不会外泄、暴露出去。也就是说作用域最大的用处就是隔离变量，不同作用域下同名变量不会有冲突。

剁椒鱼鳞

2023/05/30

1.7K0

JS基础——作用域、作用域链

go 存储容器

作用域 [[scope]]，函数定义时自动生成的一个隐式属性，是用来存储函数作用域链 Scope Chain的容器。作用域链是用来存储函数执行上下文 AO和全局执行上下文 GO的容器。函数被定义时，系统会为函数生成[[scope]]，[[scope]]中保存该函数的作用域链，并从该作用域链的起始位置开始存储当前环境的作用域链。函数被定义后&将要执行前会生成函数本身的AO，并将其插入作用域链的起始位置。函数执行完毕，相应AO也会被销毁，等待下次执行时重新生成AO，如果函数内部嵌有其他

玖柒的小窝

2021/10/22

3.6K0

作用域

c++编程算法

标识符的作用域有函数原型作用域、局部作用域（块作用域）、类作用域和命名空间（namespace）作用域

小飞侠xp

2022/05/13

9320

作用域

编程算法 java javascript ecmascript

通常来说，一段程序代码中所用到的名字（变量名）并不总是有效和可用的，而限定这个名字的可用性的代码范围就是这个名字的作用域。作用域的使用提高了程序逻辑的局部性，增强了程序的可靠性，减少了名字冲突。

星辰_大海

2020/09/30

6630

作用域

编程算法面向对象编程其他

实际上，确切地说，private访问权限被限定在class的内部，而且与方法声明顺序无关。推荐把private方法放到后面，因为public方法定义了类对外提供的功能，阅读代码的时候，应该先关注public方法：

背雷管的小青年

2020/07/08

5150

相似问题

最小不动点最大不动点

如何用两个补不动点加不动点？

Django模型:创建小值不动点

类型不动点

不动点迭代

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问如何计算程序的最坏情况(大O)
EN