DSA Big O

การฝึกซ้อมสัญลักษณ์ใหญ่ o

แนวคิดหลัก

• ความซับซ้อนของอวกาศ หมายถึงปริมาณของหน่วยความจำทางกายภาพที่อัลกอริทึมต้องการให้เสร็จสมบูรณ์
• ความซับซ้อนของเวลา หมายถึงจำนวนการดำเนินการที่อัลกอริทึมต้องดำเนินการให้เสร็จสมบูรณ์
• สัญลักษณ์ใหญ่ o เป็นวิธีการอธิบายความซับซ้อนของเวลาของอัลกอริทึม
• ความสัมพันธ์เชิงเส้น คือเมื่อสองสิ่งที่แตกต่างกัน (ตัวอย่างคือการดำเนินการและลูป) เติบโตในสัดส่วนโดยตรงและเชิงเส้นซึ่งกันและกัน
• เวลาคงที่ (O (1)) ใช้เวลาเท่ากันในการทำให้เสร็จไม่ว่าอินพุตจะใหญ่แค่ไหน "จอกศักดิ์สิทธิ์"
• เวลาลอการิทึม (O (log (n))) ใช้เวลานานขึ้นด้วยอินพุตที่ใหญ่กว่า แต่เวลาทำงานจะเพิ่มขึ้นอย่างช้าๆ ลดขนาดปัญหาครึ่งหนึ่งในแต่ละรอบ สิ่งที่ดีที่สุดถัดไปหลังจากเวลาคงที่ (O (1))
• เวลาเชิงเส้น (O (n)) มีเวลาทำงานที่เป็นสัดส่วนโดยตรงกับขนาด (n) ของอินพุต
• เวลาพหุนาม (o (n^k)) มีเวลาทำงานซึ่งจะมีขนาดอินพุตบางตัว ที่ เพิ่มขึ้นเป็นพลังงานคงที่ k
• เวลาเลขชี้กำลัง (o (2^n)) มีเวลาทำงานที่เติบโตอย่างรวดเร็วด้วยการเพิ่มขนาดอินพุต

ตัวอย่าง

• O (1) - ตัวอย่างของอัลกอริทึม O (1) กำลังเข้าถึงรายการอาร์เรย์หรือดำเนินการทางคณิตศาสตร์พื้นฐาน (เช่นเพิ่ม 2 ตัวเลข)

• O (log (n)) - ตัวอย่างที่ดีของอัลกอริทึม (O (log (n))) กำลังค้นหาผู้คนในสมุดโทรศัพท์ คุณไม่จำเป็นต้องตรวจสอบทุกคนในสมุดโทรศัพท์เพื่อค้นหาเอกสารที่ถูกต้อง แต่คุณสามารถแบ่งและพิชิตได้โดยดูตามที่ชื่อของพวกเขาเป็นตัวอักษรและในทุกส่วนคุณต้องสำรวจชุดย่อยของแต่ละส่วนก่อนที่คุณจะพบหมายเลขโทรศัพท์ของใครบางคนในที่สุด แน่นอนว่าสมุดโทรศัพท์ที่ใหญ่กว่าจะยังคงใช้เวลานานขึ้น แต่มันจะไม่เติบโตเร็วเท่าที่สัดส่วนเพิ่มขึ้นในขนาดเพิ่มเติม จำไว้ว่า:
  • ตัวเลือกองค์ประกอบถัดไปที่จะดำเนินการบางอย่างเป็นหนึ่งในความเป็นไปได้หลายประการ
  • จะต้องเลือกเพียงคนเดียวเท่านั้น หรือ
  • องค์ประกอบที่ดำเนินการเป็นตัวเลขของ n

• O (n) - ตัวอย่างบางส่วนของอัลกอริทึม O (N) กำลังสรุปองค์ประกอบในอาร์เรย์และค้นหาค่าต่ำสุดหรือสูงสุดในอาร์เรย์

• o (n^k) - วิธีที่ง่ายที่สุดในการทำความเข้าใจความซับซ้อนของเวลาพหุนามคือกับลูปซ้อนกัน อัลกอริทึมที่ต้องใช้การวนซ้ำ 2 ระดับผ่านอินพุตจะเป็น o (n^2) ในขณะที่หนึ่งที่ต้องการ 3 ระดับของการวนรอบจะเป็น o (n^3) ในทั้งสองกรณีเรามีความซับซ้อนของเวลาพหุนาม

• o (2^n) - สำหรับอินพุตขนาด 2 อัลกอริทึมเวลาเอ็กซ์โปเนนเชียลจะใช้เวลา 2^2 = 4 เวลา ด้วยอินพุตขนาด 10 อัลกอริทึมเดียวกันจะใช้เวลา 2^10 = 1024 เวลาและด้วยอินพุตขนาด 100 จะใช้เวลา 2^100 = 1.26765060022823 * 1030 เวลา อัลกอริทึมที่มีเวลาทำงาน o (2^n) มักจะเป็นอัลกอริทึมแบบเรียกซ้ำที่แก้ปัญหาขนาด n โดยการแก้ปัญหาสองปัญหาเล็ก ๆ สองขนาด N-1

กราฟความซับซ้อนของเวลา

การดำเนินงานที่ต้องการโดยความซับซ้อนของเวลาที่แตกต่างกัน

ทรัพยากร

• เสือชีต
• Web Dev Simplified
• วิดีโอความซับซ้อนในการคำนวณ CS50
• วิดีโอสัญกรณ์ Big O Hackerrank

ภาพรวมการฝึกซ้อม

ในการฝึกซ้อมเหล่านี้คุณจะฝึกการกำหนดความซับซ้อนของอัลกอริทึม สำหรับการฝึกซ้อมแต่ละครั้งเราจะจัดหาฟังก์ชั่นโค้ดและคุณจะสร้างความซับซ้อนของ O Big O โดยการวิเคราะห์รหัสโดยไม่ต้องใช้งาน

1. บิ๊กโอสำหรับสิ่งนี้คืออะไร?

1. กำหนด Big O สำหรับอัลกอริทึมต่อไปนี้: คุณกำลังนั่งอยู่ในห้องที่มี 15 คน คุณต้องการหาเพื่อนเล่นสำหรับสุนัขของคุณโดยเฉพาะอย่างยิ่งสายพันธุ์เดียวกัน ดังนั้นคุณต้องการทราบว่าใครใน 15 คนมีสายพันธุ์เดียวกับสุนัขของคุณ คุณยืนขึ้นและตะโกนออกมาที่นี่มีโกลเด้นรีทรีฟเวอร์และอยากเป็น playdate สำหรับทองคำของฉัน มีคนตะโกน - "ฉันทำมีความสุขที่จะพาเขาไป"

2. กำหนด Big O สำหรับอัลกอริทึมต่อไปนี้: คุณกำลังนั่งอยู่ในห้องที่มี 15 คน คุณต้องการหาเพื่อนเล่นสำหรับสุนัขของคุณที่เป็นสายพันธุ์เดียวกัน ดังนั้นคุณต้องการทราบว่าใครใน 15 คนมีสายพันธุ์เดียวกับสุนัขของคุณ คุณเริ่มต้นด้วยคนแรกและถามเขาว่าเขามี Retriever สีทองหรือไม่ เขาบอกว่าไม่แล้วคุณถามคนต่อไปและคนต่อไปและคนต่อไปจนกว่าคุณจะพบคนที่มีสีทองหรือไม่มีใครถาม

2. แม้แต่หรือคี่

บิ๊กโอของอัลกอริทึมต่อไปนี้คืออะไร? อธิบายคำตอบของคุณ

    if (value % 2 === 0) {
        return true;
    }
    else {
        return false;
    }
}

3. คุณอยู่ที่นี่หรือไม่?

บิ๊กโอของอัลกอริทึมต่อไปนี้คืออะไร? อธิบายคำตอบของคุณ

    for (let i = 0; i < arr1.length; i++) {
        const el1 = arr1[i];
        for (let j = 0; j < arr2.length; j++) {
            const el2 = arr2[j];
            if (el1 === el2) return true;
        }
    }
    return false;
}

4. Doubler

บิ๊กโอของอัลกอริทึมต่อไปนี้คืออะไร? อธิบายคำตอบของคุณ

    for (let i = 0; i < array.length; i++) {
        array[i] *= 2;
    }
    return array;
}

5. การค้นหาที่ไร้เดียงสา

บิ๊กโอของอัลกอริทึมต่อไปนี้คืออะไร? อธิบายคำตอบของคุณ

    for (let i = 0; i < array.length; i++) {
        if (array[i] === item) {
            return i;
        }
    }
}

6. การสร้างคู่

บิ๊กโอของอัลกอริทึมต่อไปนี้คืออะไร? อธิบายคำตอบของคุณ

    for (let i = 0; i < arr.length; i++) {
        for(let j = i + 1; j < arr.length; j++) {
            console.log(arr[i] + ", " +  arr[j] );
        }
    }
}

7. คำนวณลำดับ

อัลกอริทึมต่อไปนี้ทำอะไร? ความซับซ้อนของรันไทม์คืออะไร? อธิบายคำตอบของคุณ

    let result = [];
    for (let i = 1; i <= num; i++) {

        if (i === 1) {
            result.push(0);
        }
        else if (i === 2) {
            result.push(1);
        }
        else {
            result.push(result[i - 2] + result[i - 3]);
        }
    }
    return result;
}

8. การค้นหาที่มีประสิทธิภาพ

ในตัวอย่างนี้เรากลับไปสู่ปัญหาการค้นหาโดยใช้วิธีการที่ซับซ้อนกว่าในการค้นหาที่ไร้เดียงสาข้างต้น สมมติว่าอาร์เรย์อินพุตจะถูกจัดเรียงเสมอ บิ๊กโอของอัลกอริทึมต่อไปนี้คืออะไร? อธิบายคำตอบของคุณ

    let minIndex = 0;
    let maxIndex = array.length - 1;
    let currentIndex;
    let currentElement;

    while (minIndex <= maxIndex) {
        currentIndex = Math.floor((minIndex + maxIndex) / 2);
        currentElement = array[currentIndex];

        if (currentElement < item) {
            minIndex = currentIndex + 1;
        }
        else if (currentElement > item) {
            maxIndex = currentIndex - 1;
        }
        else {
            return currentIndex;
        }
    }
    return -1;
}

9. องค์ประกอบสุ่ม

บิ๊กโอของอัลกอริทึมต่อไปนี้คืออะไร? อธิบายคำตอบของคุณ

    return arr[Math.floor(Math.random() * arr.length)];
}

10. ฉันคืออะไร?

อัลกอริทึมต่อไปนี้ทำอะไร? บิ๊กโอของอัลกอริทึมต่อไปนี้คืออะไร? อธิบายคำตอบของคุณ

    if (n < 2 || n % 1 !== 0) {
        return false;
    }
    for (let i = 2; i < n; ++i) {
        if (n % i === 0) return false;
    }
    return true;
}

11. หอคอยฮานอย

หอคอยแห่งฮานอยเป็นปริศนาทางคณิตศาสตร์ที่มีชื่อเสียงมาก (บางเกมเรียกว่าเกม!) นี่คือวิธีที่จะไป:

• มีสามแท่งและดิสก์จำนวนมากที่มีขนาดต่างกันซึ่งสามารถเลื่อนลงบนก้านใด ๆ ปริศนาเริ่มต้นด้วยดิสก์ซ้อนกันอย่างเรียบร้อยตามลำดับขนาดของขนาดบนแท่งเดียวดิสก์ที่เล็กที่สุดที่ด้านบน (สร้างรูปทรงกรวย) อีกสองแท่งว่างเปล่าเพื่อเริ่มต้นด้วย

• เป้าหมายของปริศนาคือการย้ายสแต็คทั้งหมดของแท่งไปยังก้านอื่น (ไม่สามารถเป็นก้านดั้งเดิมที่มันถูกซ้อนกันมาก่อน) ที่มันจะซ้อนกันตามลำดับจากน้อยไปมากเช่นกัน สิ่งนี้ควรทำตามกฎต่อไปนี้:

  • สามารถเคลื่อนย้ายดิสก์เพียงครั้งเดียวได้ในแต่ละครั้ง
  • การเคลื่อนไหวแต่ละครั้งประกอบด้วยการใช้ดิสก์ด้านบนจากแท่งข้างหนึ่งและเลื่อนลงบนก้านอื่นบนดิสก์อื่น ๆ ที่อาจมีอยู่บนก้านนั้น
  • ดิสก์ขนาดใหญ่อาจไม่วางไว้บนดิสก์ขนาดเล็ก

งานของคุณ:

• หาอัลกอริทึมเพื่อแก้ปริศนาหอคอยฮานอย
• ใช้อัลกอริทึมของคุณโดยใช้การเรียกซ้ำ โปรแกรมของคุณควรแสดงการเคลื่อนไหวแต่ละครั้งของดิสก์จากแท่งหนึ่งไปยังอีกคันหนึ่ง
• หากคุณได้รับ 5 ดิสก์แท่งจะมีลักษณะอย่างไรหลังจากการโทรซ้ำ 7 ครั้ง?
• จำเป็นต้องมีการเคลื่อนไหวกี่ครั้งในการทำปริศนาด้วยดิสก์ 3 แผ่น? ด้วย 4 ดิสก์? ด้วย 5 ดิสก์?
• รันไทม์ของอัลกอริทึมของคุณคืออะไร?

12. เวอร์ชันวนซ้ำ

แก้ปัญหาการฝึกซ้อม JS 12 ซ้ำ ๆ แทนที่จะทำซ้ำ

13 Big O Big O

ใช้วิธีแก้ปัญหาจาก repo นี้และระบุความซับซ้อนของเวลา (ใหญ่ o) ของแต่ละคน

14. วนซ้ำ O O

ใช้วิธีการแก้ปัญหาของคุณจากการฝึกซ้อมซ้ำในไฟล์ JS 12 และระบุความซับซ้อนของเวลา (Big O) ของแต่ละรายการ