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
------
39
|
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
|
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...
N |
O(N) |
O(log N) |
39*O(N) |
143*O(log N)
|
2 |
2 |
1 |
78 |
143
|
4 |
4 |
2 |
156 |
286
|
8 |
8 |
3 |
312 |
429
|
16 |
16 |
4 |
624 |
572
|
32 |
32 |
5 |
1248 |
715
|
64 |
64 |
6 |
2496 |
858
|
128 |
128 |
7 |
4992 |
1001
|
256 |
256 |
8 |
9984 |
1144
|
512 |
512 |
9 |
19968 |
1287
|
1024 |
1024 |
10 |
39936 |
1430
|
String Reversal
- Suppose that we would like to reverse the characters in a string: "Theory" becomes "yroehT"
- Analysis:
- Inputs: String
- Outputs: String
- Constraints: input and output strings contain some characters, output in reverse order of input
- Assumptions: none
- Relationships: none
- For what group of strings do we immediately know a solution?
- Strings consisting of a single character
- Strings consisting of no characters
- These define our base cases
- How can we work towards these base cases?
- Remove first character
- Reverse the rest of the string
- Add the first character to the end
- This defines our recursive case
- Design
- If the string is of length zero or one, return string
- For any other string:
- Recursively call the function with the first character removed
- Concatenate to the result of the character that was removed
public String reverse(String str) {
String result;
if (str.length() <= 1) {
result = str;
} else {
result = reverse(str.substring(1)) + str.substring(0,1);
}
return result;
}
Arrays
- Arrays are an ordered collection of values
- They are objects in Java (not in C++)
- Their size is immutable
- Arrays start at position zero
- Arrays allow us to refer to an entire collection of data using a single variable name
- We can access individual values using an index variable
- Creation:
typeOfValue[] referenceVar;
referenceVar = new typeOfValue[size];
int[] iArray; // creates a reference to an array of integer values
iArray = new int[3]; // creates actual array & assigns it to iArray
Problem
- Compute the sum of the elements in an int valued array
- Analysis:
- Inputs: an array of int values
- Outputs: An integer of the sum of all values
- Constraints: None
- Assumptions: Array does not change
- Relationships: none
- Design:
- Given an array, the array's length, index of current element
- If array's length is less than or equal to the index then return zero
- Otherwise
- Recur with index plus one
- Compute and return sum of the element at index and recursive's returned value
Code
class ArraySum {
public int elementSum(int[] a) {
return doElementSum(a, 0);
}
private int doElementSum(int[] a, int index) {
int sum;
if (a.length <= index) {
sum = 0;
} else {
sum = a[index] + doElementSum(a, index+1);
}
return sum;
}
}
Array of Arrays
- It is possible to construct arrays with multiple dimensions:
int[][] a = {{1,2,3},{4,5,6},{7,8,9}};
- Alternative way to declare:
int[][] a = new int[3][];
a[0] = new int[3];
a[1] = new int[3];
a[2] = new int[3];
a[0][0] = 1;
a[0][1] = 2;
a[0][2] = 3;
a[1][0] = 4;
...
- Note: Each row can be a different length
Array Searching
- Suppose that we want to know the position of the largest value in an array (the last position, if multiple occurrences)
- We could search linearly to find it
- Possible approach:
- Assume value in position 0 is largest
- Compare to next value:
- If no more values, done
- If next value is larger or equal, make it the largest so far
- If next value is smaller, repeat
Code
public int posOfLargest(int[] a, int pol, int index) {
int result;
if (index >= a.length) {
result = pol;
} else if (a[pol] > a[index]) {
result = posOfLargest(a, pol, index+1);
} else {
result = posOfLargest(a, index, index+1);
}
return result;
}
CIS 3020 Part 8