Complexity & Searching

โจทย์เดียวกันเขียนได้หลายวิธี แต่ละวิธีใช้จำนวน step ไม่เท่ากัน Complexity analysis คือการวัดว่าเมื่อข้อมูล n โตขึ้น จำนวน step โตเร็วแค่ไหน

อัลกอริทึม 2 แบบ ผลเท่ากันแต่คนละราคา

โจทย์: บวกเลข 1 ถึง n

Algor1(n){
    sum = 0
    for(i = 1 to n){
        sum = sum + i
    }
    return sum
}

1,  2,  3,  … ,  n-2,  n-1,  n

จับคู่หัวท้าย: 1+n = n+1, 2+(n-1) = n+1, …
ได้ n+1 ทั้งหมด n/2 คู่  →  ผลรวม = (n+1)(n/2)

Algor2(n){
    return (n+1)*(n/2)
}

นับจำนวน step ยังไง

for (i = 0 to n)
{
    a = i+1
    print(a)
}

ข้างในลูปนับเป็น 1 step ลูปวน i = 0 ถึง n จึงได้

Σi=0..n 1 = n + 1        →  O(n+1) = O(n)
Σi=0..n c = n + c        →  O(n+c) = O(n)

วิธีวิเคราะห์ 2 แบบ

long start = System.nanoTime();
// code algorithm → searching X in array A size n
long stop  = System.nanoTime();

เทียบอัตราการโตด้วย limit

อยากรู้ว่า f(n) กับ g(n) ตัวไหนโตเร็วกว่า ให้หาลิมิตของอัตราส่วน

lim (n→∞) f(n)/g(n) =
    ∞   → f(n) โตเร็วกว่า g(n)
    0   → g(n) โตเร็วกว่า f(n)
    C   → โตเท่ากัน

lim log(n)/n²
  = lim ln(n) / (ln10 · n²)
  = (1/ln10) · lim (1/n) / (2n)      // L'Hôpital: หาอนุพันธ์ทั้งเศษและส่วน
  = (1/ln10) · lim 1/(2n²)
  = 0

ลำดับการโตที่ต้องจำ:

O(1) << O(log n) << O(n) << O(n²) << O(2ⁿ)

Big-O และเพื่อน ๆ

กฎการตัดทอน

O(n+1) = O(n) + O(1)     // O(1) โตช้ากว่า O(n)
O(n+1) = O(n)            // เก็บเฉพาะพจน์ที่โตเร็วสุด
O(n+c) = O(n)
O((n²-n)/2) = O(n²)      // ตัดค่าคงที่คูณทิ้ง

Linear Search

for (i = 0 to n)
{
    if(x[i] == c)
    {
        return i
    }
}

ไล่ดูทีละช่องจากซ้ายไปขวา

Binary Search

เงื่อนไขสำคัญ: ข้อมูลต้องเรียงแล้ว ถ้าไม่เรียง binary search ใช้ไม่ได้

ตัวอย่าง: array [1, 6, 7, 9, 10, 12, 15, 16, 17] ค้นหา 16

Linear search ใช้ 8 ครั้ง ส่วน binary search ใช้ 3 ครั้ง

search(a, x, left, right)
{
    // เงื่อนไขหยุด: เหลือช่องเดียว
    if(left == right){
        if(a[left] == x) print("found at " + x);
        return;
    }
    // เงื่อนไขหยุด: เหลือ 2 ช่องสุดท้าย
    if(left == right-1){
        if(a[left]  == x) { print("found at " + x); return; }
        if(a[right] == x) { print("found at " + x); return; }
    }

    mid = left + ((right - left)/2)

    if(a[mid] == x){
        print("found at " + x);
        return;
    }
    if(x > a[mid])  search(a, x, mid+1, right);
    if(x < a[mid])  search(a, x, left, mid);
}

แก้ recurrence ของ Binary Search

แต่ละรอบข้อมูลลดลงครึ่งหนึ่ง และเสียงานคงที่ c ต่อรอบ

T(n)   = T(n/2¹) + c
T(n/2) = T(n/2²) + c
T(n/4) = T(n/2³) + c
    …
T(n/2^(k-1)) = T(n/2^k) + c
T(n/2^k) = b            // รอบสุดท้าย เหลือ 1 ตัว

รอบสุดท้ายเหลือข้อมูล 1 ตัว จึงได้

n/2^k = 1
n     = 2^k
k     = log₂ n          // จำนวนรอบ

โปรแกรมทำงาน k รอบ = log n รอบ → O(log n)

n = 8  →  8 → 4 → 2 → 1   ลึก 3 ชั้น
8 = 2³ ดังนั้นชั้น = 3 = log₂ 8

สรุปเทียบ 2 อัลกอริทึม