Java开发网 - 懂Big O邏籍的高手请进~

Topic: 懂Big O邏籍的高手请进~

1.懂Big O邏籍的高手请进~

Posted by: ProJava
Posted on: 2003-11-25 12:08

以下都是哪種Big O 邏籍阿, 謝謝~

1. int sum = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n * 2 - 6; c++) {
sum = sum + s[r][c];
}
}
我猜是O(n^2)

2. int sum = 0;
for (int r = n / 2; r < n; r++) {
for (int c = n * 2 - 6; c < n * 2; c++) {
sum = sum + s[r][c];
}
}
我猜是O( n )

3.
if (a < b) {
n = n*n;
} else {
while (n > 0) {
x = x + 2;
n = n / 2;
}
}
我猜是O(n^2)

4.
int sum = 0;
int x = n;
while(x > 0) {
for (int i = 0; i < x; i++) {
sum = sum + s[i];
}
for (int j = x; j > 0; j--) {
sum = sum + s[j - 1];
}
x = x / 2;
}

我猜是O( n )

謝謝喔~

2.Re:懂Big O邏籍的高手请进~ [Re: ProJava]	Copy to clipboard
Posted by: dorrenchen Posted on: 2003-11-25 23:08 3. should be O(log(n)), since n=n/2 4. should be O(log(n) * n), because 1st for loop runs n operation, and so is 2nd one. So each while loop runs 2n operations. and since x = x/2, so while loop will be run log(n) times. so total number of operation is: log(n) * 2n, and constant 2 is eliminated in big O notation.

3.Re:懂Big O邏籍的高手请进~ [Re: ProJava]	Copy to clipboard
Posted by: dorrenchen Posted on: 2003-11-25 23:09 smilies!! 3. should be O(log), since n=n/2 4. should be O(log * n), because 1st for loop runs n operation, and so is 2nd one. So each while loop runs 2n operations. and since x = x/2, so while loop will be run log times. so total number of operation is: log * 2n, and constant 2 is eliminated in big O notation.

4.Re:懂Big O邏籍的高手请进~ [Re: ProJava]	Copy to clipboard
Posted by: dorrenchen Posted on: 2003-11-25 23:11 smilies ate my "(n)"!!! 3. should be O(log(n)), since n=n/2 4. should be O(log(n) * n), because 1st for loop runs n operation, and so is 2nd one. So each while loop runs 2n operations. and since x = x/2, so while loops will run log(n) times. so total number of operation is: log(n) * 2n, and constant 2 is eliminated in big O notation.

5.Re:懂Big O邏籍的高手请进~ [Re: ProJava]	Copy to clipboard
Posted by: alin_ass Posted on: 2003-11-25 23:17 it论坛没必要搞笑脸的

6.Re:懂Big O邏籍的高手请进~ [Re: ProJava]	Copy to clipboard
Posted by: floater Posted on: 2003-11-25 23:56 check on this: 禁止在这个帖子中使用笑脸标记 before you reply it, this will get rid of those smiling faces. I disable it for you.

7.Re:懂Big O邏籍的高手请进~ [Re: ProJava]	Copy to clipboard
Posted by: ProJava Posted on: 2003-11-26 04:39 謝謝指導~ 感謝!!

8.Re:懂Big O邏籍的高手请进~ [Re: ProJava]

Copy to clipboard

Posted by: ProJava
Posted on: 2003-11-26 04:45

小弟還有一個問題 : 碰到這種問題怎麼找BigO啊? 謝謝~

For each method shown below give a big-O bound for its running time. Assume get and set are O(1). For addAll assume the methods of c and c's iterator are O(1). Give the bounds in terms of only the capacity, size and c's size.

import java.util.Collection;
import java.util.Iterator;

public class SquareList implements Collection {

private Object[][] elements;
private int side;
private int size;

public SquareList(int capacity) {
side = (int)Math.max(Math.ceil(Math.sqrt(capacity)), 1);
elements = new Object[side][];
}

public void clear() {
for (int row = 0; row < size / side; ++row) {
elements[row] = null;
}
size = 0;
}

public boolean add(Object o) {
add(size, o);
return true;
}

public void add(int i, Object o) {
if (size % side == 0) {
elements[size / side] = new Object[side];
}
++size;
for (int j = size - 1; j > i; --j) {
set(j, get(j - 1));
}
set(i, o);
}

public boolean addAll(Collection c) {
Iterator ci = c.iterator();
while (ci.hasNext()) {
add(ci.next());
}
return !c.isEmpty();
}
}

再次感謝~

9.Re:懂Big O邏籍的高手请进~ [Re: ProJava]	Copy to clipboard
Posted by: dorrenchen Posted on: 2003-11-26 12:51 Each addAll() runs c.size() times. Each add() runs 1 time, I think the for loop doesn't get executed at all, since j=++size -1 = original size, and i=size. so total is O(c.size()) times for allAll() some strange code

10.Re:懂Big O邏籍的高手请进~ [Re: ProJava]	Copy to clipboard
Posted by: ProJava Posted on: 2003-11-27 09:14 我想我懂一些了, 真的很感謝這位大哥, 謝謝

11.Re:懂Big O邏籍的高手请进~ [Re: ProJava]

Copy to clipboard

Posted by: ProJava
Posted on: 2003-11-28 12:57

還有一些疑問, 如果碰到連結表單(Linked List)時, bigO又是怎麼做啊, 謝謝~

例如 1: Print the middle item in a linked list of n items.
例如 2: Print the first item in a linked list of n items.
例如 3: Print all the items in a LinkedArrayList of size n, using get(int) to get each one.

(原問題如下 :
For these three problems, give your answer in terms of n. Assume that once an item is accessed, the call to print is O(1).

1.Print the middle item in a linked list of n items.
2.Print the first item in a linked list of n items.
3.Print all the items in a LinkedArrayList of size n, using get(int) to get each one.

)

懇請指點迷津, 再三感謝~

12.Re:懂Big O邏籍的高手请进~ [Re: ProJava]

Copy to clipboard

Posted by: dorrenchen
Posted on: 2003-12-02 02:28

1. 1/2 of all items are accessed, so answer is O(n), disregard constant 1/2.

2. only once. O(1).

3. ok, so get(1) takes 1 operation, get(2) takes 2, ... get(n) takes n. after get() is being called for n times, number of total operations from all get() calls is (1+n)/2 * n = 0.5*(n^2) + 0.5 * n, disregard 2nd term (0.5 * n), and disregard constant, answer is O(n^2)