CIS 3020 Part 5
Contents
Messy Example 1
Code
ass Mess1 { public static void main (String[] arg) { int d; d=10; System.out.println(d); Ex1 g; g=new Ex1(); g.a(d); System.out.println(d); } } class Ex1 { int p; Ex1() { p=0; } public void a (int p) { this.b(p); this.printVals(p); this.b(this.p); } private void b (int q) { this.printVals(q); } private void printVals(int r) { System.out.println(r); } }
Output
10 10 10 0 10
Messy Example 2
Code
class Mess2 { public static void main (String[] arg) { int d,e; d=4; e=6; System.out.println(d + " " + e); Ex2 g = new Ex2(); g.a(d,e); System.out.println(d + " " + e); } } class Ex2 { int p; Ex2() { p=3; } public void a (int p, int r) { this.b(r,p); this.printVals(p,r); this.b(this.p,r); } private void b (int p, int r) { this.printVals(p,r); this.printVals(this.p,r); } private void printVals(int p, int r) { System.out.println(p + " " + r); } }
Output
4 6 6 4 3 4 4 6 6 3 3 3 4 6
Messy Example 3
Code
class Mess3 { public static void main (String[] arg) { int d,e; d=4; e=6; System.out.println(d + " " + e); Ex3 g = new Ex3(); g.a(d,e); System.out.println(d + " " + e); } } class Ex3 { int p; Ex3() { p=3; } public void a (int p, int r) { this.b(r,p); this.printVals(p,r); this.b(r,this.p); } private void b (int p, int r) { this.printVals(r, this.p); c(p,r); c(this.p, r); } void c(int r, int p) { this.printVals(p,r); } private void printVals(int p, int r) { System.out.println(p + " " + r); } }
Messy Example 4
Code
class Mess4 { public static void main (String[] arg) { int d,e,f; d=4; e=6; f=8; System.out.println(d + " " + e + " " + f); Ex4 g = new Ex4(); g.a(d,e,f); System.out.println(d + " " + e + " " + f); } } class Ex4 { int p; Ex4() { p=3; } public void a (int p, int q, int r) { b(q,r,p); this.printVals(p,q,r); this.b(r,q,this.p); } private void b(int p, int q, int r) { this.printVals(p,q,r); c(this.p, q, r); c(p,r,q); } void c(int q, int p, int r) { this.printVals(p,q,r); } private void printVals(int p, int q, int r) { System.out.println(p + " " + q + " " + r); } }
Tree Recursion
- Consider the Fibonacci Number Sequence:
- This sequence is defined by the rule:
/ 0 when n=0 fib(n)= | 1 when n=1 \ fib(n-1) + fib(n-2) otherwise
- As code this is:
public int fib (int n) { int result; if (n<=0) result = 0; else if (n == 1) result = 1; else result = (fib(n-1) + fib(n-2)); return result; }
Orders of Growth
- An important consideration in the comparison of different soluytions to problems is the complexity of the algorithms used.
- This complexity is measured on two important quantities:
- The space requirements (space complexity) to represent all values used in the algorithm
- The time requirements (time complexity) needed to perform all of the needed calculations
The BIG-O
- Informal Definition
- If function Est(n) times some integer constant, m, dominates funciton Time(n), then we say:
- Time(n) = O(Est(n))
Algebraic Identities for Big-O
Assume c denotes a constant and that f and g are arbitrary functions
- c * f = O(f) -- you can drop constant multipliers
17n = O(n) 25n² = O(n²) 99 = O(1)
- f + g = O(f), so long as f dominates g