Difference between revisions of "CIS 3020 Part 7"
Jump to navigation
Jump to search
| Line 30: | Line 30: | ||
2 | 2 | ||
| − | ======= | + | ===Exponentiation, O(log N)=== |
| − | + | {| | |
| + | |- | ||
| + | | | ||
| + | <pre> | ||
| + | public int expt(int b, int n) { | ||
| + | return fastExpt(b,n); | ||
| + | } | ||
| + | |||
| + | private int fastExpt(int b, int n) { | ||
| + | int result; | ||
| + | if (n<=0) result = 1; | ||
| + | else if (even(n)) result = square(fastExpt(b, n/2)); | ||
| + | else result = b * fastExpt(b, n-1); | ||
| + | return result; | ||
| + | } | ||
| + | |||
| + | private int square(int x) { | ||
| + | return (x * x); | ||
| + | } | ||
| + | |||
| + | private boolean even(int x) { | ||
| + | return (x % 2 == 0); | ||
| + | } | ||
| + | |||
| + | </pre> | ||
| + | || | ||
| + | <pre> | ||
| + | 2 | ||
| + | 23 | ||
| + | |||
| + | |||
| + | 2 | ||
| + | 1 | ||
| + | 6 | ||
| + | 67 | ||
| + | 28 | ||
| + | 2 | ||
| + | |||
| + | |||
| + | 1 | ||
| + | 4 | ||
| + | |||
| + | |||
| + | 1 | ||
| + | 6 | ||
| + | ====== | ||
| + | 143 | ||
</pre> | </pre> | ||
|} | |} | ||
| + | ===Comparison=== | ||
| + | * some might argue that the second method is ~3.7 times as expensive | ||
| + | * And, even if it is O(log N), it will be slower than the first method | ||
| + | * Let's look at values to see if this is true... | ||
| + | |||
===Exponentiation, O(log N)=== | ===Exponentiation, O(log N)=== | ||
{| | {| | ||
Revision as of 10:06, 26 April 2007
Complexity
- When computing O(), we are concerned with big values of n
- With big values, constants become ignorable
- Consider the two exponential functions we developed
- Let's count all operations (arithmetic, assignment, references, comparisons, etc.) the same with calls counting 20.
Exponentiation, O(N)
public int expt(int b, int n) {
int result;
if (n<=0) {
result = 1;
} else {
result = b * expt(b, n-1);
}
return result;
}
|
2
1
3
3
28
2
===Exponentiation, O(log N)===
{|
|-
|
<pre>
public int expt(int b, int n) {
return fastExpt(b,n);
}
private int fastExpt(int b, int n) {
int result;
if (n<=0) result = 1;
else if (even(n)) result = square(fastExpt(b, n/2));
else result = b * fastExpt(b, n-1);
return result;
}
private int square(int x) {
return (x * x);
}
private boolean even(int x) {
return (x % 2 == 0);
}
|
2 23 2 1 6 67 28 2 1 4 1 6 ====== 143 |
Comparison
- some might argue that the second method is ~3.7 times as expensive
- And, even if it is O(log N), it will be slower than the first method
- Let's look at values to see if this is true...
Exponentiation, O(log N)
public int expt(int b, int n) {
return fastExpt(b,n);
}
private int fastExpt(int b, int n) {
int result;
if (n<=0) result = 1;
else if (even(n)) result = square(fastExpt(b, n/2));
else result = b * fastExpt(b, n-1);
return result;
}
private int square(int x) {
return (x * x);
}
private boolean even(int x) {
return (x % 2 == 0);
}
|
2 23 2 1 6 67 28 2 1 4 1 6 ====== 143 |
