ผลต่างระหว่างรุ่นของ "204512-53/lecture2"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 19: แถว 19:
 
                  
 
                  
 
                 A[j+1] = x
 
                 A[j+1] = x
 +
 +
===Loop Invariants===
 +
  1. I จริงก่อนทำ (Initialization)
 +
  2. ทุกๆรอบหลัง loop ทำเสร็จ I ก็จริง (Maintainance)
 +
  3. ถ้า loop จบการทำงาน +I (Yermination)
 +
  เป้าหมายก็คือโปรแกรมถูกต้องตรงกับ termination ที่เราต้องการ
  
 
=BIG O=
 
=BIG O=

รุ่นแก้ไขเมื่อ 05:17, 8 กรกฎาคม 2553

Loop Invariants

  • การเรียงข้อมูล
  1. Insertion Sort
  2. Bubble Sort

Insertion

Algorithm

  1.   for i = 2  to  n       (พิจารณาข้อมูล array A[i])
  2.   x  A[i]  , j  (i - 1)
  3.   While (i > 0) and (A[j] > x)
               
                A[j+1]  A[j]
                
                j  j-1
                
                A[j+1] = x

Loop Invariants

  1. I จริงก่อนทำ (Initialization)
  2. ทุกๆรอบหลัง loop ทำเสร็จ I ก็จริง (Maintainance)
  3. ถ้า loop จบการทำงาน +I (Yermination)
  เป้าหมายก็คือโปรแกรมถูกต้องตรงกับ termination ที่เราต้องการ 

BIG O

Definition

     function f(n) เป็น O(g(n)) หรือ f(n) = O(g(n)) 
     ถ้ามี n0 และ c(คือค่าคงที่) ที่ 
     f(n) ≤ c.g(n)    โดยที่ n   ≥  n0

ตัวอย่าง กราฟ Big O

BigO.jpg

ตัวอย่าง1

พิสูจน์ 1000n = O(n2)

ถ้า n > 1000 n2 ≥ 1000n

ให้ n0 = 1001 , c = 1 1000n ≤ 1n2

เมื่อ n ≥ 1001

Binary Search Tree

Red-Black Trees

  • เป็น Binary tree
  • Assume ว่าทุก node จบลงที่ Nil Node(All leaf node is Nil)

เงื่อนไข

  • Node ใดๆจะเป็นสีแดงไม่ก็ดำ
  • Root เป็นสีดำ
  • Leaf เป็นสีดำ
  • Node ใดเป็น Red Node Child ของ Node นั้นจะต้องเป็น Black Node
  • จาก Node u ใดๆทุกๆ Path จาก Node ดังกล่าวไปยัง Leaf ของมันจะต้องมี Node ที่เป็นสีดำเท่ากันทั้งหมด

Lemma

Red-Black tree ที่มี n internal nodes จะมีความสูงไม่เกิน 2log(n+1)

Proof

นิยาม ที่ Node u ใดๆ bh(u) (black height ของ u) จะเท่ากับจำนวน Black Node จาก u ไป Node Leaf ใดๆ(ไม่นับ u))

Claim

สำหรับ internal node u ใดๆจำนวน internal node ใน sub-tree ใดๆที่ u เป็น rootจะมีค่าไม่น้อยกว่า 2^bh(u) -1

Proof (By induction)

ให้ w = u.left และ h = u.right

     bh(w) ≥ bh(u) – 1
     bh(x) ≥ bh(u) – 1

โดย Induction

     Sub-tree ของ w มี internal node ≥ 2^bh(w) -1 ≥ 2^(bh(u)-1)  -1
     Sub-tree ของ x มี internal node ≥ 2^bh(x) -1 ≥ 2^(bh(u)-1)  -1

ดังนั้น internal node ของ u = 1 + 2^(bh(u)-1) -1 + 2^(bh(u)-1) -1 = 2^bh(u) -1

พิจารณา Red-Black Tree ใดๆสูง h

bh(h) ≥ h/2 (เนื่องจาก Red Node จะต้องตามด้วย Black Node เสมอ)

จะได้ Internal node (n)

     n 	≥ 2^bh(h) -1
     n 	≥ 2^(h/2)-1
     n+1       ≥ 2^(h/2)
     log(n+1)  ≤ h/2
     h	       ≤2log(n+1)