具有多个变量的Big O分析 [英] Big O Analysis with Multiple Variables

问题描述

我发现了这个Big O分析问题，并了解到您可以拥有一个具有多个变量的Big O.

I found this Big O analysis question and learned that you can have a Big O with more than one variable.

void f3(int n, int m, int r) {
        for (int i = 0; i < n; ++i) {                   O(N)
            for (int j = m; m > 0; m /= 2) {            O(log(M))   

            }
        }
    }
Answer: O(N log M)

问题1 :阅读 Big O有两个变量相乘的变量，我想知道是否准确地说:只有在有多个参数的情况下，Big O中才可能有多个变量

Question 1 After reading Big O with 2 variables which multiply together, I am wondering if it is accurate to say that: it is only possible for there to be more than one variable in Big O only if there are multiple parameters.

我不确定，因为从我发现的结果来看，具有多个变量的Big O似乎并不是很常见，大多数答案都针对通常的单变量Big O分析.

I am unsure because Big O with multiple variables doesn't seem to be very common at-least from what I could find, most answers address the usual single variable Big O analysis.

问题2 应将具有多个变量的Big O保持不变，还是根据增长更快的变量进行简化?

Question 2 Should Big O with multiple variables be kept as they are or simplified based on whichever variable grows faster?

我能找到的最佳答案来自方法的大O分析 ，答案基本上是说要保留每个变量，除非您可以确定哪个变量增长最快，在这种情况下您要丢弃其他变量.我不知道答案的准确性如何.

The best answer I could find was from Big O analysis for method with multiple parameters, where the answer basically says to leave each of the variables unless you can determine which variable grows fastest in which case you drop the other variables. I don't know how accurate the answer is though.

推荐答案

我想知道是否准确地说:只有在有多个参数的情况下，Big O中才可能有多个变量.

I am wondering if it is accurate to say that: it is only possible for there to be more than one variable in Big O only if there are multiple parameters.

不，那是不正确的.您可以从单个参数派生多个变量.例如:

No, that's not accurate. You can derive multiple variables from a single parameter. For example:

• a = n
中以10为基数的数字
• b = n
的基数2表示中的1位数目
• c = n 和 m
的最大公约数

• a = the number of base 10 digits in n
• b = the number of 1 bits in the base 2 representation of n
• c = the greatest common divisor of n and m

或者，如果有字符串参数 s :

Or, if there were a string parameter s:

• d = s
的长度
• e = s
中的单词数
• f = s
中的行数
• g = s
中的元音数量

• d = the length of s
• e = the number of words in s
• f = the number of lines in s
• g = the number of vowels in s

应该将具有多个变量的Big O保持不变，还是根据增长更快的变量进行简化?

Should Big O with multiple variables be kept as they are or simplified based on whichever variable grows faster?

有时您可以简化多变量公式，但我不会说您应该做到这一点.不要将多个变量视为有害的东西，可以避免.如果多个变量可以更好地描述问题，或者提供更紧密的界限，或者更易于使用，请使用多个变量.

Sometimes you can simplify a multi-variable formula, but I wouldn't say you should do it. Don't think of multiple variables as something harmful to be avoided. If multiple variables better characterize the problem, or provide a tighter bound, or are easier to work with, then use multiple variables.

例如，将两个矩阵相乘的成本取决于两者的大小.自然地，有多个变量在起作用，试图减少它们的数量毫无意义.如果我想知道计算两个集合的交集需要多长时间，则需要知道每个集合中有多少个项目.一个有用的Big-O公式将具有两个变量，这是自然而不可避免的.

For instance, the cost of multiplying two matrices is dependent on the size of both. There are naturally multiple variables in play, and it'd be pointless to try to reduce their number. If I want to know how long it takes to compute the intersection of two sets, I need to know how many items are in each of them. A useful Big-O formula will have two variables, it's natural and unavoidable.

这篇关于具有多个变量的Big O分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！