社区首页 >问答首页 >图的时间和空间复杂度表示

问图的时间和空间复杂度表示
EN

Stack Overflow用户

提问于 2020-05-14 09:33:14

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

我想知道为什么图算法的时间和空间复杂度大多是用比V和E，而不是V和E来表示的，其他算法的时间和空间复杂度都是用普通字母(如N或NlogN )表示的。为什么图算法是用类似于mod的方式来表示的？

graph

time-complexity

space-complexity

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-05-14 11:06:05

在图算法中，E和V都是集合，而不是数字。E是边的集合，V是顶点的集合。

复杂性函数是数值函数。在log(E)或E^2中没有任何意义，除非您参考了集合的大小。这正是绝对值对集合所做的，|X|是指集合X的大小。这意味着，|E|和|V|分别是图中的边数和顶点数。

当您通常看到n时，它意味着输入的大小。在图中，我们将其拆分为|V|和|E|。图形的一个常见符号是使用|V|=n和|E|=m，然后使用n,m，就像在其他地方一样。

票数 1

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

原文链接：

https://stackoverflow.com/questions/61803742

复制

时间复杂度和空间复杂度

编程算法

这个算法的运行次数函数是f (n) =3。根据我们推导大0阶的方法，第一步就是把常数项3 改为1。在保留最高阶项时发现，它根本没有最高阶项，所以这个算法的时间复杂度为0(1)。

周三不加班

2019/09/04

1.1K0

时间复杂度和空间复杂度详解

编程算法

（1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

全栈程序员站长

2022/07/15

1.4K0

算法的时间复杂度和空间复杂度计算

https 网络安全编程算法

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)= O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度，是一种“渐进表示法”。其中f(n)是问题规模n的某个函数。

全栈程序员站长

2022/08/28

2.4K0

算法的时间复杂度和空间复杂度-总结[通俗易懂]

编程算法

通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。因此，作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。

全栈程序员站长

2022/08/27

1.5K0

算法的时间复杂度和空间复杂度笔记

编程算法

蛮三刀酱

2019/09/10

1.1K0

时间复杂度和空间复杂度详解原

其他

wuweixiang

2018/08/14

7550

时间复杂度O(n)和空间复杂度

编程算法

算法对于敲代码的应该都听过，不管是复杂的还是简单的，衡量算法效率的两个重要指标就是时间复杂度和空间复杂度。

wade

2020/04/24

7720

时间复杂度和空间复杂度如何计算出来_代码时间复杂度和空间复杂度

https 网络安全 html 编程算法

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n}=0(f(n))。它表示随问题规模n的增大，算法执行时间的埔长率和 f(n)的埔长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f( n)是问题规横n的某个函数。

全栈程序员站长

2022/11/17

6290

【时间复杂度空间复杂度】

数据结构磁盘递归函数算法

当文件没有进行保存时，这个文件保留在内存中，一旦断电，文件将无法保存，因此为了避免这种情况的发生，，处理文件之后，应该及时的ctrl+s保存到磁盘当中去。

每天都要进步呀

2023/03/28

1.7K0

漫谈时间复杂度/空间复杂度

数据结构 python

碰到一个问题，总是心心念，因为我不信一个问题没有解决之道。。。只是时间，地点，人物不合适，所以导致无法解决。。。接口总比方法多。

SRE运维实践

2019/07/08

7460

时间复杂度与空间复杂度

编程算法

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。那么我们应该如何去衡量不同算法之间的优劣呢？

LittlePanger

2020/04/14

8980

常见排序算法的时间复杂度和空间复杂度表

排序算法

lexingsen

2022/02/25

1.2K0

【数据结构】时间和空间复杂度

数据结构递归函数算法效率

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间。算法中的基本操作的执行次数，为算法的时间复杂度。

xxxflower

2023/04/16

9210

时间复杂度与空间复杂度

编程算法 java

在计算机程序编写前，依据统计方法对算法进行估算，经过总结，我们发现一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素：

Rochester

2020/09/01

6180

时间复杂度与空间复杂度

编程算法

可以看出当N为3时，一共递归了3次，每次递归函数调用一次即时间复杂度为O(N)

lovevivi

2022/11/10

3350

「时间」与「空间」复杂度

编程算法二叉树

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，比如排序就有前面的十大经典排序和几种奇葩排序，虽然结果相同，但在过程中消耗的资源和时间却会有很大的区别，比如快速排序与猴子排序：）。

小小詹同学

2019/11/12

6710

数据结构之时间复杂度和空间复杂度

数据结构函数数学算法效率

我们都知道算法是处理数据的方法，那么如何衡量一个算法的好坏呢？（即，判断该算法的效率如何）由于算法在编写成可执行程序后，运行会消耗时间资源和空间（内存）资源，因此衡量一个算法的好坏一般通过时间和空间两个维度进行衡量。即，时间复杂度和空间复杂度。

摘星

2023/04/28

3000

算法的时间复杂度与空间复杂度

编程算法

一、说明时间复杂度和空间复杂度是用来评价算法效率高低的2个标准，身为开发者肯定会经常会听到这2个概念，但它们分别是什么意思呢? 其实这两个概念从字面意思上也能看出一二：时间复杂度：就是说执行算法需

Umbrella1024

2021/02/28

1.6K0

算法的时间复杂度与空间复杂度

程序函数数组算法效率

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。例如之前的斐波那契数：

有礼貌的灰绅士

2023/03/28

1.1K0

点击加载更多

相似问题

图的邻接表表示的空间复杂度

时间复杂度和空间复杂度

计算时间和空间复杂度

算法时间和空间复杂度

算法复杂度:时间和空间

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问图的时间和空间复杂度表示
EN