以图作为输入的算法的多项式与伪多项式复杂度
Polynomial vs. pseudo-polynomial complexity for an algorithm with a graph as input
在分析以图为输入的算法的复杂性时，我很难区分多项式运行时间和伪多项式运行时间。
图表有|A|圆弧和|V|顶点。该算法的复杂度为 O(|A|*K^2)，其中 K 是某个常数。
复杂度多项式还是伪多项式？并且取决于图是指定为邻接表还是邻接矩阵？
简短回答：对于邻接列表，该算法绝对是多项式的（因此是伪多项式的），对于邻接矩阵，它取决于 'dense' 图的方式。
首先，伪多项式或多项式的定义是什么？
要制定算法，我们需要某种方法以机器可读的形式对输入进行编码。在最理论的版本中，这意味着作为图灵机的输入。如果我们有一个具有 n 个顶点和 m 个边的图，我们可以编写以下表示（类似于边列表）：
n#u1,v1#u2,v2#...#um,vm
其中 ui 是起始顶点的编号，vi 是第 i 条边的结束顶点的编号。
如果我们使用数字的二进制表示（即数字 k 占用 O(log k) space），那么我们的整个图可以表示为长度为L = O(log n * m)
如果我们使用一元表示，我们的输入词的长度为 L = O(n * m)。
多项式（或伪多项式）意味着如果我们的输入数字表示为二进制（或一元）数字，则您的算法对于某个固定的 k 最多需要 O(L^k) 时间。
回到你的问题
您的算法的运行时间为 O(m)（Big-O 表示法中可以省略常量），对于邻接列表（使用 O(log n * m) space).
对于邻接矩阵（使用 O(n²) space），这仅在我们对边数有一些渐近下界时才有效，但如果我们至少有 Ω(n) 条边则肯定有效（例如，如果图形是连通的）。
在分析以图为输入的算法的复杂性时，我很难区分多项式运行时间和伪多项式运行时间。
图表有|A|圆弧和|V|顶点。该算法的复杂度为 O(|A|*K^2)，其中 K 是某个常数。
复杂度多项式还是伪多项式？并且取决于图是指定为邻接表还是邻接矩阵？
简短回答：对于邻接列表，该算法绝对是多项式的（因此是伪多项式的），对于邻接矩阵，它取决于 'dense' 图的方式。
首先，伪多项式或多项式的定义是什么？
要制定算法，我们需要某种方法以机器可读的形式对输入进行编码。在最理论的版本中，这意味着作为图灵机的输入。如果我们有一个具有 n 个顶点和 m 个边的图，我们可以编写以下表示（类似于边列表）：
n#u1,v1#u2,v2#...#um,vm
其中 ui 是起始顶点的编号，vi 是第 i 条边的结束顶点的编号。
如果我们使用数字的二进制表示（即数字 k 占用 O(log k) space），那么我们的整个图可以表示为长度为L = O(log n * m)
如果我们使用一元表示，我们的输入词的长度为 L = O(n * m)。
多项式（或伪多项式）意味着如果我们的输入数字表示为二进制（或一元）数字，则您的算法对于某个固定的 k 最多需要 O(L^k) 时间。
回到你的问题
您的算法的运行时间为 O(m)（Big-O 表示法中可以省略常量），对于邻接列表（使用 O(log n * m) space).
对于邻接矩阵（使用 O(n²) space），这仅在我们对边数有一些渐近下界时才有效，但如果我们至少有 Ω(n) 条边则肯定有效（例如，如果图形是连通的）。