Difference between revisions of "CIS 3020 Part 5"

From In The Wings
Jump to navigation Jump to search
 
(3 intermediate revisions by the same user not shown)
Line 210: Line 210:
  
 
# c * f = O(f) -- you can drop constant multipliers
 
# c * f = O(f) -- you can drop constant multipliers
<pre>
+
: <code>17n = O(n)</code>
17n = O(n)
 
  
25n² = O(n²)
+
: <code>25n² = O(n²)</code>
  
99 = O(1)
+
: <code>99 = O(1)</code>
</pre>
 
 
<ol start="2">
 
<ol start="2">
 
<li>f + g = O(f), so long as f dominates g
 
<li>f + g = O(f), so long as f dominates g
 
</ol>
 
</ol>
: n² + 3 = O(n²)
+
: <code>n² + 3 = O(n²)</code>
  
: n<sup>5</sup> + n<sup>3</sup> + n = O(n<sup>5</sup>)
+
: <code>n<sup>5</sup> + n<sup>3</sup> + n = O(n<sup>5</sup>)</code>
 
<ol start="3">
 
<ol start="3">
 
<li>f * g = O(f) * O(g)
 
<li>f * g = O(f) * O(g)
 
</ol>
 
</ol>
<pre>
+
: <code>n<sup>3</sup>m² = O(n<sup>3</sup>) * O(m²)</code>
n<sup>3</sup>m² = O(n<sup>3</sup>) * O(m²)
+
==Important Order Relationships==
</pre>
+
for the following assume that k and c are positive constants and that n is a variable
 +
{| border = "1"
 +
|-
 +
| n<sup>n</sup> || dominates n!
 +
|-
 +
| n! || dominates c<sup>n</sup>
 +
|-
 +
| c<sup>n</sup> || dominates k<sup>n</sup>, so long as c>k
 +
|-
 +
| k<sup>n</sup> || dominates k<sup>c</sup>, so long as k>1
 +
|-
 +
| n<sup>c</sup> || dominates n<sup>k</sup>, so long as c>k
 +
|-
 +
| n<sup>2</sup> || dominates n * log(n)
 +
|-
 +
| n * log(n) || dominates n
 +
|-
 +
| n || dominates log(n)
 +
|-
 +
| log(n) || dominates 1
 +
|}
 +
==Special Big-O Complexities==
 +
* A complexity of O(1) is called ''Constant Complexity''
 +
* A complexity of O(N) is called ''Linear Complexity''
 +
* A complexity of O(N<sup>K</sup>) is called ''Polynomial Complexity''
 +
* Any complexity dominating O(2<sup>N</sup>) is called ''Exponential Complexity''
 +
==Growth of Complexity Functions==
 +
{| border="1"
 +
! log(n) !! n !! n * log(n) !! n<sup>2</sup> !! n<sup>3</sup> !! 2<sup>n</sup>
 +
|-
 +
| 0 || 1 || 0 || 1 || 1 || 2
 +
|-
 +
| 1 || 2 || 2 || 4 || 8 || 4
 +
|-
 +
| 2 || 4 || 8 || 16 || 64 || 16
 +
|-
 +
| 3 || 8 || 24 || 64 || 512 || 256
 +
|-
 +
| 4 || 16 || 64 || 256 || 4096 || 65536
 +
|-
 +
| 5 || 32 || 160 || 1024 || 32768 || 4294967296
 +
|-
 +
| 6 || 64 || 384 || 4096 || 262144 || (Note 1)
 +
|-
 +
| 7 || 128 || 896 || 16384 || 2097152 || (Note 2)
 +
|-
 +
| 8 || 256 || 2048 || 65536 || 16777216 || ?????
 +
|}
 +
# Approximately the number of machine instructions executed on a 1 gigaflop (10<sup>9</sup>) supercomputer in 5000 years.
 +
# Approximately 500 billion times the age of the universe (in nanoseconds: 10<sup>-9</sup>)
 +
==[[CIS 3020 Part 6]]==

Latest revision as of 11:23, 2 April 2007

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:
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
  • 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

  1. c * f = O(f) -- you can drop constant multipliers
17n = O(n)
25n² = O(n²)
99 = O(1)
  1. f + g = O(f), so long as f dominates g
n² + 3 = O(n²)
n5 + n3 + n = O(n5)
  1. f * g = O(f) * O(g)
n3m² = O(n3) * O(m²)

Important Order Relationships

for the following assume that k and c are positive constants and that n is a variable

nn dominates n!
n! dominates cn
cn dominates kn, so long as c>k
kn dominates kc, so long as k>1
nc dominates nk, so long as c>k
n2 dominates n * log(n)
n * log(n) dominates n
n dominates log(n)
log(n) dominates 1

Special Big-O Complexities

  • A complexity of O(1) is called Constant Complexity
  • A complexity of O(N) is called Linear Complexity
  • A complexity of O(NK) is called Polynomial Complexity
  • Any complexity dominating O(2N) is called Exponential Complexity

Growth of Complexity Functions

log(n) n n * log(n) n2 n3 2n
0 1 0 1 1 2
1 2 2 4 8 4
2 4 8 16 64 16
3 8 24 64 512 256
4 16 64 256 4096 65536
5 32 160 1024 32768 4294967296
6 64 384 4096 262144 (Note 1)
7 128 896 16384 2097152 (Note 2)
8 256 2048 65536 16777216 ?????
  1. Approximately the number of machine instructions executed on a 1 gigaflop (109) supercomputer in 5000 years.
  2. Approximately 500 billion times the age of the universe (in nanoseconds: 10-9)

CIS 3020 Part 6