我有一个有大量边到顶点n(n-1)/2的图。如果我有16次眩晕,16^2 + 120是376,120 * log2(16)是480。所以V^2在这里更快?我的计算正确吗?如果它们是正确的,那么顶点的大小什么时候才能到达E log v更快的点?
发布于 2014-04-16 10:51:54
渐近表示法告诉您,随着输入的增长,执行时间是如何增长的,这不允许您进行类似的比较,比如“对于V = 10, E = 15,我得到的值比另一个小”。
如果有两种算法,具有时间复杂性O(V^2 + E)和O(E log V),那么唯一可以说的是,第一种算法对稠密图更有效,而对稀疏图则更好(假设V^2 = E用于稠密图,V = E用于稀疏图)。
https://stackoverflow.com/questions/23106488
复制相似问题