de algorismoKratui++
IMOS Method I : หนึ่งมิติ
  • IMOS Method* : เป็นการต่อยอดเทคนิกการบวกสะสม**
    เพื่อใช้กับมิติที่สูงขึ้นและจำนวนลำดับที่มากขึ้น


    IMOS Method แบบพื้นฐานที่สุดคือการบวกในหนึ่งอาเรย์มิติ

    รูปที่ ๑ แสดงการเพิ่มค่าข้อมูลลงในอาเรย์หนึ่งมิติ

    ปัญหา คุณเปิดร้านกาแฟ สำหรับทุกลูกค้า i เข้าร้านในเวลา Si และออกในเวลา Ei (0 ≤ Si <Ei ≤ T)
    ให้ค่า M คือจำนวนที่ลูกค้าอยู่ในร้าน ณ เวลาหนึ่ง ๆ จงหาค่า M ที่มากที่สุด

    วิธีแก้ปัญหาที่บ้านนอกที่สุด คือการไล่บวกแม่งทุกตัว (C แทนจำนวนลูกค้า และ T แทนเวลาทำการ) อัลกอฯนี้มี O(CT) ซึ่งแน่นอนว่าโจทย์ให้ C กับ  T มาล้านเศษแน่นอน รับประกันว่าวิธีนี้จะติด T รัว ๆ

    1. for (int i = 0; i < T; i++)
    2. table[i] = 0;
    3. for (int i = 0; i < C; i++) {
    4. // Read note 1
    5. for (int j = S[i]; j < E[i]; j++) {
    6. table[j]++;
    7. }
    8. }
    9. // Read note 2
    10. M = 0;
    11. for (int i = 0; i < T; i++) {
    12. if (M < table[i]) M = table[i];
    13. }
    Note 1: ไล่บวกจำนวนลูกค้าในช่วงเวลาที่ลูกค้าอยู่ไปทีละคน
    Note 2: หาจำนวนลูกค้าที่มากที่สุดจากทุกช่วงเวลา

    แต่ถ้าใช้ IMOS อัลกอฯนี้จะเหลือ O(C+T) เท่านั้น วิธีการคือบวกจำนวนลูกค้าในช่วงเวลาที่ลูกค้าเข้ามาและลบจำนวนลูกค้าออกในเวลาที่ลูกค้าออกจากร้านเท่านั้น เช่น
    มีลูกค้า C1 {S = 1, E = 3}, C2 {2, 4}, C3 {3, 4} จะได้ว่าในเวลา 1<=T<=4 จะมีจำนวนลูกค้าดังนี้
    + C1 :   1, 0, -1, 0
    + C2 :   1, 1, -1, -1
    + C3 :   1, 1, 0, -2
    จากนั้น เกลี่ย จำนวนของลูกค้าด้วยวิธีเดียวกับ Quick Sum คือ N(Tn) += N(Tn-1) | n > 0  จึงเป็น
    1, 2, 2, 0
    ซึ่งถ้าใช้วิธีแรกก็จะได้คำตอบเดียวกันในช่วง [S, E)

    1. for (int i = 0; i < T; i++)
    2. table[i] = 0;
    3. for (int i = 0; i < C; i++) {
    4. table[S[i]]++; // Read note 1
    5. table[E[i]]--; // Read note 2
    6. }
    7. // Read note 3
    8. for (int i = 1; i < T; i++)
    9. table[i] += table[i - 1];

    10. // Read note 4
    11. M = 0;
    12. for (int i = 0; i < T; i++)
    13. if (M < table[i]) M = table[i];
    Note 1: บวกจำนวนลูกค้าในเวลาที่มีลูกค้าเข้ามา ไม่บวกไล่ไปเหมือนวิธีแรก
    Note 2: ลบจำนวนลูกค้าเมื่อลูกค้าออก
    Note 3: เกลี่ย จำนวนลูกค้าในทุกช่วงเวลา
    Note 4: หาจำนวนลูกค้าที่มากที่สุดจากทุกช่วงเวลา


    ติดตามต่อ EP. II มิติที่สูงขึ้น

    * (จากคำว่า いもす法; เอาตรง ๆ คือไม่รู้จะแปลชื่อมันว่าอะไร)
    **(รู้จักในชื่อ Quick Sum)
    อ้างอิงจาก https://imoz.jp/algorithms/imos_method.html
    ได้รับอนุญาติให้เผยแพร่เป็นภาษาไทยจาก @imos เจ้าของเว็บไซต์อ้างอิง
Views

เข้าสู่ระบบเพื่อแสดงความคิดเห็น

Log in