棘手的Big

本文介绍了棘手的Big-O复杂性的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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).