棘手的Big-O复杂性 [英] Tricky Big-O complexity

问题描述

public void foo(int n, int m) {
    int i = m;

    while (i > 100) {
        i = i / 3;
    }
    for (int k = i ; k >= 0; k--) {
        for (int j = 1; j < n; j *= 2) {
            System.out.print(k + "\t" + j);
        }
        System.out.println();
    }
}

我认为复杂度为O(logn).
那是内循环(外循环)的产物-绝不会执行超过100次，因此可以省略.

我不确定while子句，是否应该将其合并到Big-O复杂性中?对于很大的 i 值，它可能会产生影响或进行算术运算，无论在多大程度上都无关紧要，可以算作基本运算且可以省略?

解决方案

while循环为O(log m)，因为您一直将m除以3，直到其小于或等于100. >

因为在您的情况下100是常数，所以可以忽略它.

内部循环如您所说是O(log n)，因为您将j与2相乘，直到超过n.

因此，总复杂度为O(log n + log m).

或算术运算，无论在多大程度上都算作基本运算，可以省略吗?

通常可以省略算术运算，是的.但是，这也取决于语言.这看起来像Java，看起来好像您正在使用基本类型.在这种情况下，可以考虑算术运算O(1)，是的.但是，例如，如果使用大整数，那将不再可行，因为加法和乘法不再是O(1).

public void foo(int n, int m) {
    int i = m;

    while (i > 100) {
        i = i / 3;
    }
    for (int k = i ; k >= 0; k--) {
        for (int j = 1; j < n; j *= 2) {
            System.out.print(k + "\t" + j);
        }
        System.out.println();
    }
}

I figured the complexity would be O(logn).
That is as a product of the inner loop, the outer loop -- will never be executed more than 100 times, so it can be omitted.

What I'm not sure about is the while clause, should it be incorporated into the Big-O complexity? For very large i values it could make an impact, or arithmetic operations, doesn't matter on what scale, count as basic operations and can be omitted?

解决方案

The while loop is O(log m) because you keep dividing m by 3 until it is below or equal to 100.

Since 100 is a constant in your case, it can be ignored, yes.

The inner loop is O(log n) as you said, because you multiply j by 2 until it exceeds n.

Therefore the total complexity is O(log n + log m).

or arithmetic operations, doesn't matter on what scale, count as basic operations and can be omitted?

Arithmetic operations can usually be omitted, yes. However, it also depends on the language. This looks like Java and it looks like you're using primitive types. In this case it's ok to consider arithmetic operations O(1), yes. But if you use big integers for example, that's not really ok anymore, as addition and multiplication are no longer O(1).

这篇关于棘手的Big-O复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！