Is O(mn) in O(n^2)?

Question

简单的问题。使用 m x n 矩阵，我正在做一些 O（mn） 操作。我的问题是 O（mn） 是否在 O（n^2） 中。看着大O上的维基百科，我会这么认为，但我在复杂性方面一直很糟糕，所以我希望有人能澄清一下。

Answer 1

O（mn） 表示m x n矩阵意味着您正在对矩阵的每个值执行恒定的工作。

O（n^2） 表示，对于每一列，您正在执行 O（# 列）的工作。请注意，此运行时随着行数 # 而略有增加。

所以，最后，这是一个m是否大于n的问题。 如果 m>> n，则 O（n^2） 更快。 如果 m <<n，O（mn） 更快。

Answer 2

如果m是O（n），m * n是O（n²）。

我假设对于矩阵，您可能会有 m = O（n），这是列数，而n是行数。所以m * n = O（n²）。但是谁知道你的矩阵会有多少列。

这完全取决于m有什么界限。

看看O（n）的定义。