O(mn)是否在O(n ^ 2)中?

本文介绍了O(mn)是否在O(n ^ 2)中?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

一个简单的问题.使用m x n矩阵，我正在执行一些O(mn)运算.我的问题是O(mn)是否在O(n ^ 2)中.在大O上查看Wikipedia，我会这样想，但是我在复杂性方面一直很糟糕，所以我希望有人能澄清一下.

Simple question. Working with an m x n matrix and I'm doing some O(mn) operations. My question is if O(mn) is in O(n^2). Looking at the Wikipedia on big O I would think so but I've always been pretty bad at complexity bounds so I was hoping someone could clarify.

推荐答案

O(mn)意味着您要对矩阵的每个值进行恒定的工作.

O(mn) for a m x n matrix means that you're doing constant work for each value of the matrix.

O(n ^ 2)表示，对于每一列，您正在做的工作是O(#列).请注意，此运行时间随行数的增加而增加.

O(n^2) means that, for each column, you're doing work that is O(# columns). Note this runtime increases trivially with # of rows.

因此，最后，问题是 m 是否大于 n .如果m >> n，则O(n ^ 2)更快.如果m<<n，O(mn)更快.

So, in the end, it's a matter of if m is greater than n. if m >> n, O(n^2) is faster. if m << n, O(mn) is faster.