主页 / 问题 / 1321072
Accepted
Demon __
Asked:2022-08-25 04:27:07 +0800 CST2022-08-25 04:27:07 +0800 CST

这个大 O 到底是什么意思：O(|E|)

  • 772

我参加了BIG O测试并得到了这个问题：

发生矩阵 -> 发生矩阵

Graph Operations: Incidence Matrix
Query

O(|V| + |E|)
O(1)
O(|E|) -> правильный ответ
O(|V|)
O(|V|²)
O(|V| ⋅ |E|)

问题是这么大的 O: 是什么意思O(|E|)？

例如，这里没有这样的困难。

математика

2 个回答

  1. Best Answer

    这样的 Big Os 是图上算法的典型代表。

    经典名称：

    • |V|-V图中的顶点数
    • |E|- 图中的边E数

    因此，这O(|E|)意味着该算法具有取决于图边数的线性复杂度。

    提供的链接包含与图上的算法无关的算法示例，其中大多数使用n“输入数据”作为大小。一个典型的例子是列表\树\任何其他数据结构中的元素数量。

    对于图上的算法，“输入数据”的两个非常不同的参数是典型的：顶点数和边数，将计算复杂度（Big O）分解为这些分量非常有用。

    注意：

    根据定义，图是有序对G(V,E)。因此，|V|- 是顶点集的基数，|E|- 是边集的基数，其中基数应该被理解为对“集合的元素数量”的抽象概括。

    • 11

  2. 有一个算法。它需要许多参数作为输入：a、b、c...

    该算法在时间 t(a, b, c, ...) 中运行。

    如果存在一个常数 C 使得对于任何 a, b, c, ... 我们有不等式，则称一个算法在 O(f(a, b, c, ...)) 中运行：

    t(a, b, c, ...)<C*f(a, b, c, ...)

    在你的情况下 a=E, b=V, f=|E|

    • 3

相关问题