首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >哪个时间复杂度更快(V^2 + E)或(E log V)

问哪个时间复杂度更快(V^2 + E)或(E log V)
EN

Stack Overflow用户
提问于 2014-04-16 10:16:31
回答 1查看 1.5K关注 0票数 2

我有一个有大量边到顶点n(n-1)/2的图。如果我有16次眩晕,16^2 + 120是376,120 * log2(16)是480。所以V^2在这里更快?我的计算正确吗?如果它们是正确的,那么顶点的大小什么时候才能到达E log v更快的点?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-04-16 10:51:54

渐近表示法告诉您,随着输入的增长,执行时间是如何增长的,这不允许您进行类似的比较,比如“对于V = 10, E = 15,我得到的值比另一个小”。

如果有两种算法,具有时间复杂性O(V^2 + E)和O(E log V),那么唯一可以说的是,第一种算法对稠密图更有效,而对稀疏图则更好(假设V^2 = E用于稠密图,V = E用于稀疏图)。

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

https://stackoverflow.com/questions/23106488

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档