សញ្ញា Big-O

មាតិកា

1. Big-O និយាយអ្វីពិតប្រាកដ
2. បោះចោលថេរ
3. O(1)៖ ពេលវេលាថេរ
4. O(log n)៖ ពេលវេលា Logarithmic
5. O(n)៖ ពេលវេលា Linear
6. O(n log n)៖ ដែនដីនៃការតម្រៀប
7. O(n^2)៖ ការអាន Loop ជ្រៅ
8. O(2^n)៖ ពេលវេលា Exponential
9. ករណីល្អបំផុត អាក្រក់បំផុត និងជាមធ្យម
10. ការវាស់ពេលវេលាពិត
11. includes ទល់នឹង Set.has
12. Linear Search ទល់នឹង Binary Search
13. Space Complexity
14. រូបមន្ត៖ Module bench
15. សាកល្បងដោយខ្លួនឯង

1. Big-O និយាយអ្វីពិតប្រាកដ

ទំព័ររបស់អ្នកផ្ទុកក្នុងមួយប៉ព្រិចជាមួយអ្នកប្រើ 100 នាក់។ ជាមួយអ្នកប្រើ 100,000 នាក់ វាប្រើពេលមួយនាទី។ តើអ្វីបានផ្លាស់ប្តូរ? មិនមែនកូដទេ គឺគ្រាន់តែទំហំនៃទិន្នន័យ។ សញ្ញា Big-O គឺជាវិធីពិពណ៌នាថាតើការងាររបស់កម្មវិធី លូតលាស់ យ៉ាងណាពេល input លូតលាស់។

វាមិនប្រាប់អ្នកថាអ្វីមួយប្រើពេលប៉ុន្មានមីលីវិនាទីទេ។ វាប្រាប់អ្នកអំពី រូបរាង នៃខ្សែកោងការលូតលាស់ ជារូបរាងដូចគ្នាពី Function, ការលូតលាស់ និង Logarithm។ អាន O(n) ថា "លំដាប់នៃ n"៖ ប្រសិនបើ input មាន n ធាតុ ការងារលូតលាស់សមាមាត្រនឹង n។

នេះគឺជារូបរាងទូទៅ ពីល្អបំផុតទៅអាក្រក់បំផុត ជាមួយចំនួនជំហានដែលនីមួយៗត្រូវការ៖

(n^2 មានន័យថា n * n។ តម្លៃ log ត្រូវបានបង្គត់ឡើង ហើយ n log n គឺ n គុណ log2(n)។)

សូមមើលជួរចុងក្រោយ។ មួយលានធាតុជាមួយ algorithm O(n^2) គឺមួយទ្រីលានជំហាន ដែលជាច្រើនម៉ោងឬច្រើនថ្ងៃ។ Algorithm O(n log n) ធ្វើការងារដូចគ្នាក្នុងរយៈពេលតិចជាងមួយវិនាទី។ ការជ្រើសរើស algorithm ត្រឹមត្រូវសំខាន់ជាងការទិញ server លឿនជាងឆ្ងាយ។

2. បោះចោលថេរ

Big-O រក្សាតែផ្នែកដែលគ្របដណ្តប់ពេល n ធំ ហើយមិនអើពើនឹងអ្វីដែលនៅសល់។ ច្បាប់ពីរ៖

1. បោះចោលមេគុណថេរ។ ប្រសិនបើ loop មួយធ្វើប្រតិបត្តិការ 3 ក្នុងមួយធាតុ ហើយមួយទៀតធ្វើ 1 ទាំងពីរគឺ O(n)។ 3n និង n មានរូបរាងដូចគ្នា៖ បន្ទាត់ត្រង់។
2. បោះចោលតួតូចៗ។ n^2 + n គឺគ្រាន់តែ O(n^2) ព្រោះពេល n = 1,000,000 ផ្នែក n^2 គឺមួយទ្រីលាន ហើយ n បន្ថែមគឺគ្រាន់តែជាកំហុសបង្គត់។

function example(items) {
  let count = 0;

  for (const a of items) count++;           // n ជំហាន
  for (const a of items) count += 2;        // n ជំហាន
  for (const a of items) {                  // n * n ជំហាន
    for (const b of items) count++;
  }

  return count;
}
// សរុប: n + n + n*n = n^2 + 2n  ->  O(n^2)

នេះមើលទៅធ្វេសប្រហែស ហើយវាធ្វើដោយចេតនា។ ថេរពឹងផ្អែកលើម៉ាស៊ីន, ភាសា និងថ្ងៃ។ រូបរាងនៃខ្សែកោងមិនពឹងផ្អែកទេ។

ការប្រុងប្រយ័ត្នមួយ៖ ថេរ មាន សារៈសំខាន់ក្នុងការអនុវត្តពេល n តូច។ សម្រាប់ 10 ធាតុ algorithm O(n^2) ដែលមានថេរតូចអាចយកឈ្នះ algorithm O(n log n) ឆ្លាតវៃ។ Big-O គឺអំពីអ្វីដែលកើតឡើងពេលទិន្នន័យបន្តលូតលាស់។

3. O(1)៖ ពេលវេលាថេរ

O(1) មានន័យថាការងារមិនអាស្រ័យលើ n ទាល់តែសោះ។ ការអានធាតុ array តាម index, ការរកមើល key ក្នុង object ឬ Map ឬការបូកលេខពីរ ទាំងអស់ប្រើពេលប្រហែលគ្នា មិនថាបណ្តុំមានដប់ធាតុ ឬដប់លានធាតុឡើយ។

const ids = [101, 102, 103, 104, 105];
console.log(ids[0]);              // 101
console.log(ids[ids.length - 1]); // 105

ទាំងពីរបន្ទាត់គឺ O(1)៖ កុំព្យូទ័រលោតត្រង់ទៅទីតាំងដោយប្រើនព្វន្ត ហើយមិនដើរកាត់បញ្ជីទេ។ លេខ 1 មិនមែនមានន័យថា "មួយជំហាន" ទេ។ វាមានន័យថា "ចំនួនជំហានថេរ"។

4. O(log n)៖ ពេលវេលា Logarithmic

O(log n) មានន័យថារាល់ជំហានបោះចោលប្រភាគធំមួយ (ជាទូទៅពាក់កណ្តាល) នៃអ្វីដែលនៅសល់។ អ្នកបានជួបវាក្នុងជំពូកមុន៖ binary search។

function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Loop ដំណើរការ log2(n) ដងព្រោះជួរ low..high ថយពាក់កណ្តាលរាល់ពេល។ មួយលានធាតុត្រូវការ loop យ៉ាងច្រើនបំផុត 20 ជុំ មួយពាន់លានត្រូវការ 30។ ពេលណាអ្នកឃើញ loop ដែលបញ្ហាដែលនៅសល់ត្រូវ កាត់ពាក់កណ្តាល (ឬតាមប្រភាគថេរណាមួយ) សូមគិតដល់ O(log n)។

សញ្ញាបញ្ជាក់៖ n = n / 2 នៅក្នុង loop ឬ i *= 2 ជាជំហាន loop។

function countHalvings(n) {
  let count = 0;
  while (n > 1) {
    n = Math.floor(n / 2);
    count++;
  }
  return count;
}

console.log(countHalvings(1_000_000)); // 19
console.log(countHalvings(1024));      // 10

5. O(n)៖ ពេលវេលា Linear

O(n) មានន័យថាអ្នកប៉ះគ្រប់ធាតុប្រហែលម្តង។ ទិន្នន័យទ្វេដង ការងារទ្វេដង។ ការបូកបញ្ជី, ការរកតម្លៃធំបំផុត ឬការពិនិត្យថា array មានអ្វីមួយឬអត់ ទាំងអស់គឺ linear។

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

console.log(linearSearch([40, 10, 30, 20], 30)); // 2
console.log(linearSearch([40, 10, 30, 20], 99)); // -1

ក្នុងករណីអាក្រក់បំផុត (target នៅចុងក្រោយ ឬបាត់) វាមើលទាំង n ធាតុ។ Built-in ជាច្រើនជា linear ដោយមិនប្រាប់អ្នក៖ array.includes, array.indexOf, array.find, array.filter, array.map និង array.reduce សុទ្ធតែដើរកាត់ array។

អន្ទាក់ទូទៅរបស់អ្នកចាប់ផ្តើមគឺការលាក់ជំហាន linear ក្នុង loop មួយទៀត ដែលបំលែង O(n) ទៅជា O(n^2)៖

// សម្រាប់រាល់ order រកអតិថិជនរបស់វា: មើលទៅដូច loop មួយ ប៉ុន្តែ .find ក៏ដើរកាត់ដែរ។
for (const order of orders) {
  const customer = customers.find((c) => c.id === order.customerId);
}

ប្រសិនបើបញ្ជីទាំងពីរមាន n ធាតុ នោះគឺ n * n ជំហាន។ សាងសង់ Map នៃអតិថិជនតាម id តែម្តង (O(n)) បន្ទាប់មករកមើលនីមួយៗក្នុង O(1) ហើយការងារទាំងមូលក្លាយជា O(n)។

6. O(n log n)៖ ដែនដីនៃការតម្រៀប

O(n log n) គឺអ្វីដែលអ្នកទទួលបានពេលអ្នកធ្វើការងារ O(log n) មួយចំណែកសម្រាប់ដល់ទាំង n ធាតុ ឬបំបែកទិន្នន័យជាពាក់កណ្តាលម្តងហើយម្តងទៀត ហើយធ្វើការងារ linear នៅគ្រប់កម្រិត។ ការតម្រៀបគោលបំណងទូទៅដែលល្អគឺជាឧទាហរណ៍បុរាណ៖ array.sort() របស់ JavaScript គឺ O(n log n)។

const nums = [5, 2, 9, 1, 7];
const sorted = [...nums].sort((a, b) => a - b);
console.log(sorted); // [ 1, 2, 5, 7, 9 ]
console.log(nums);   // [ 5, 2, 9, 1, 7 ] (ដើមមិនប៉ះពាល់)

[...nums] ធ្វើច្បាប់ចម្លងជាមុន ព្រោះ sort ផ្លាស់ប្តូរ array ដែលវាត្រូវបានហៅលើ។ ផ្នែក (a, b) => a - b ត្រូវការសម្រាប់លេខ៖ បើគ្មានវា sort ប្រៀបធៀបធាតុជាអក្សរ ហើយ 10 នឹងតម្រៀបមុន 2។

អ្នកអាចមើលឃើញរូបរាងដោយរាប់ loop ដែលដំណើរការ n ដងជាមួយ loop ខាងក្នុងដែលកើនទ្វេដង៖

function nLogN(n) {
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < n; j *= 2) count++;
  }
  return count;
}

console.log(nLogN(1024)); // 10240 (នោះគឺ 1024 * 10)

O(n log n) គ្រាន់តែអាក្រក់ជាង linear បន្តិចប៉ុណ្ណោះ។ ការតម្រៀបមួយលានធាតុប្រើប្រហែល 20 លានជំហានមូលដ្ឋាន ដែលកុំព្យូទ័រយួរដៃធ្វើក្នុងរយៈពេលតិចជាងមួយវិនាទី។ វាគឺជាតម្លៃនៃទិន្នន័យដែលមានលំដាប់ ហើយទិន្នន័យមានលំដាប់គឺជាអ្វីដែលធ្វើឱ្យ binary search O(log n) អាចទៅរួច។

7. O(n^2)៖ ការអាន Loop ជ្រៅ

Loop នៅក្នុង loop ដែលនីមួយៗដំណើរការលើ n ធាតុដូចគ្នា ផ្តល់ O(n^2)។ តួខាងក្នុងដំណើរការ n * n ដង៖

function countPairs(items) {
  let count = 0;
  for (let i = 0; i < items.length; i++) {
    for (let j = 0; j < items.length; j++) {
      count++;
    }
  }
  return count;
}

console.log(countPairs([1, 2, 3, 4, 5]));      // 25
console.log(countPairs(new Array(10).fill(0))); // 100

Input ទ្វេដង ការងារបួនដង៖ 5 ធាតុផ្តល់ 25, 10 ធាតុផ្តល់ 100។ នេះជាមគ្គុទ្ទេសក៍រហ័សសម្រាប់អាន loop៖

មានបំរែបំរួលទូទៅមួយដែល loop ខាងក្នុងចាប់ផ្តើមបន្ទាប់ពី loop ខាងក្រៅ (j = i + 1) ដូចពេលពិនិត្យគ្រប់គូដើម្បីរកស្ទួន៖

function countUniquePairs(n) {
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      count++;
    }
  }
  return count;
}

console.log(countUniquePairs(5));   // 10
console.log(countUniquePairs(100)); // 4950

វាដំណើរការ n * (n - 1) / 2 ដង ដែលសម្រាប់ n = 100 គឺ 4,950។ វាប្រហែលពាក់កណ្តាលនៃ n^2 ប៉ុន្តែពាក់កណ្តាលគឺជាថេរ ដូច្នេះវានៅតែជា O(n^2)។

ឧទាហរណ៍ជាក់ស្តែងមួយគឺការរកតម្លៃស្ទួន។ កំណែនេះប្រៀបធៀបគ្រប់គូ៖

function hasDuplicateSlow(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

កំណែនេះចងចាំអ្វីដែលវាបានឃើញក្នុង Set ហើយជា O(n)៖

function hasDuplicateFast(arr) {
  const seen = new Set();
  for (const item of arr) {
    if (seen.has(item)) return true;
    seen.add(item);
  }
  return false;
}

អ្នកដោះដូរអង្គចងចាំជាមួយពេលវេលា។ យើងនឹងវាស់ទាំងពីរក្នុងបន្តិចទៀត។ (type Set មកដោយផ្ទាល់ពី សំណុំ និងប្រតិបត្តិការសំណុំ។)

8. O(2^n)៖ ពេលវេលា Exponential

O(2^n) ធ្វើឱ្យការងារទ្វេដងសម្រាប់រាល់ធាតុបន្ថែម។ ជាធម្មតាវាលេចឡើងពេលកូដព្យាយាម គ្រប់បន្សំ ឬ recurse ពីរដងក្នុងមួយការហៅ។ fib ឆោតល្ងង់ពីជំពូកមុនគឺជាឧទាហរណ៍មួយ។ មួយទៀតគឺការបង្កើតគ្រប់ subset នៃបញ្ជី៖

function subsets(items) {
  if (items.length === 0) return [[]];
  const [first, ...rest] = items;
  const without = subsets(rest);
  const with_ = without.map((s) => [first, ...s]);
  return [...without, ...with_];
}

console.log(subsets([1, 2, 3]).length);       // 8
console.log(subsets([1, 2, 3, 4]).length);    // 16
console.log(subsets([1, 2, 3]));
// [ [], [ 3 ], [ 2 ], [ 2, 3 ], [ 1 ], [ 1, 3 ], [ 1, 2 ], [ 1, 2, 3 ] ]

សម្រាប់ n ធាតុ មាន 2^n subset។ សាមសិបធាតុផ្តល់លើសពីមួយពាន់លាន ហុកសិបធាតុមិនអាចបញ្ចប់ក្នុងជីវិតរបស់អ្នកទេ។ ប្រសិនបើកិច្ចការមួយហាក់ដូចជាត្រូវការ O(2^n) សូមរកវិធីឆ្លាតជាងនេះ (ដូចជាការចងចាំចម្លើយមុនៗ) ឬទទួលយកលទ្ធផលប្រហាក់ប្រហែល។

រូបរាងពាក់ព័ន្ធដែលអាក្រក់ជាងនេះទៅទៀតគឺ O(n!) ដូចជាការសាកល្បងគ្រប់លំដាប់នៃ n ធាតុ។ អ្នកនឹងជួបវានៅក្នុង ការរាប់៖ Permutation និង Combination។

9. ករណីល្អបំផុត អាក្រក់បំផុត និងជាមធ្យម

កូដដដែលអាចប្រើកម្លាំងខុសគ្នាអាស្រ័យលើទិន្នន័យ។ យក linearSearch៖

• ករណីល្អបំផុត៖ target ជាធាតុទីមួយ។ មួយជំហាន O(1)។
• ករណីអាក្រក់បំផុត៖ target នៅចុងក្រោយ ឬបាត់។ n ជំហាន O(n)។
• ករណីជាមធ្យម៖ អ្នកមើលតាមប្រហែលពាក់កណ្តាលបញ្ជី n / 2 ជំហាន ដែលនៅតែជា O(n) ពេលអ្នកបោះចោលថេរ។

ពេលមនុស្សនិយាយថា "នេះគឺ O(n)" ដោយគ្មានលក្ខខណ្ឌ ពួកគេស្ទើរតែតែងតែមានន័យថា ករណីអាក្រក់បំផុត។ នោះគឺជាការធានាដែលអ្នកអាចគ្រោងតាម៖ វានឹងមិនអាក្រក់ជាងនេះឡើយ។

Binary search ក៏ដូចគ្នា៖ ករណីល្អបំផុតគឺត្រូវចំកណ្តាលលើកដំបូង (ការប្រៀបធៀបមួយ) ករណីអាក្រក់បំផុតគឺប្រហែល log2(n) ដង។ សូម្បីតែករណីអាក្រក់បំផុតសម្រាប់មួយលានធាតុក៏មានតែ 20។

10. ការវាស់ពេលវេលាពិត

Big-O គឺជាការទស្សន៍ទាយ។ ដើម្បីឃើញអ្វីដែលកើតឡើងពិតប្រាកដ ត្រូវវាស់។ Node ផ្តល់ឧបករណ៍ងាយៗពីរដល់អ្នក។

console.time និង console.timeEnd បោះពុម្ពពេលវេលាដែលកន្លងផុតជាមួយ label៖

const numbers = Array.from({ length: 1_000_000 }, (_, i) => i);

console.time("sum");
let total = 0;
for (const n of numbers) total += n;
console.timeEnd("sum"); // sum: 4.1ms (លេខរបស់អ្នកនឹងខុស)
console.log(total);     // 499999500000

performance.now() ត្រឡប់ timestamp ភាពច្បាស់ខ្ពស់ជាមីលីវិនាទី ដូច្នេះអ្នកអាចដកការអានពីរ ហើយប្រើលទ្ធផលក្នុងកូដ៖

const start = performance.now();
let total = 0;
for (let i = 0; i < 1_000_000; i++) total += i;
const elapsed = performance.now() - start;
console.log(`took ${elapsed.toFixed(2)} ms`); // took 1.30 ms (ប្រែប្រួល)

ការព្រមានដោយស្មោះត្រង់ខ្លះអំពី benchmark៖

• ពេលវេលាប្រែប្រួល ពីម៉ាស៊ីនមួយទៅម៉ាស៊ីនមួយ និងសូម្បីតែពីការដំណើរការមួយទៅមួយ។ ទុកចិត្ត សមាមាត្រ រវាងការវាស់ពីរ មិនមែនលេខពិតប្រាកដទេ។
• ការដំណើរការលើកដំបូងច្រើនតែយឺតជាង ខណៈ engine កំពុងឡើងកម្តៅ។ ធ្វើការងារម្តងទៀត ហើយមើលការដំណើរការជាច្រើនដង។
• ប្រតិបត្តិការលឿនខ្លាំងត្រូវធ្វើម្តងទៀត (ឧទាហរណ៍ 100 ឬ 1,000 ដង) ដើម្បីផលិតលេខធំជាងសំឡេងរំខានរបស់ timer។
• វាស់ទំហំទិន្នន័យជាក់ស្តែង។ Input តូចលាក់ភាពខុសគ្នារវាងរូបរាងការលូតលាស់។

11. includes ទល់នឹង Set.has

តើ array.includes(x) មើលគ្រប់ធាតុឬទេ? បាទ/ចាស៖ វាជា O(n)។ តើ set.has(x) មើលគ្រប់ធាតុឬទេ? ទេ៖ Set សាងសង់លើ hash table ហើយឆ្លើយក្នុងប្រហែល O(1) ជាមធ្យម។ តោះសាកល្បងជាមួយមួយលានធាតុ ដោយរកធាតុចុងក្រោយ 100 ដង៖

const arr = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
const set = new Set(arr);
const target = arr[arr.length - 1]; // ករណីអាក្រក់បំផុតសម្រាប់ array

let start = performance.now();
for (let i = 0; i < 100; i++) arr.includes(target);
console.log("includes:", (performance.now() - start).toFixed(2), "ms");

start = performance.now();
for (let i = 0; i < 100; i++) set.has(target);
console.log("Set.has: ", (performance.now() - start).toFixed(4), "ms");
// includes: 14.20 ms
// Set.has:  0.0268 ms   (លេខនឹងខុសនៅលើម៉ាស៊ីនរបស់អ្នក)

នៅលើកុំព្យូទ័រយួរដៃធម្មតា Set លឿនជាងរាប់រយដងនៅទីនេះ ហើយគម្លាតកាន់តែធំពេលបណ្តុំកាន់តែធំ។ Array ធ្វើការដើរកាត់ 100 ជុំលើមួយលានធាតុ ចំណែក Set ធ្វើការរកមើលលឿន 100 ដង។

ការដោះដូរ៖ ការសាងសង់ Set ចំណាយពេល និងអង្គចងចាំ។ ប្រសិនបើអ្នករកម្តង array គឺល្អគ្រប់គ្រាន់។ ប្រសិនបើអ្នករកច្រើនដង សាងសង់ Set តែម្តង។ នោះគឺជារបៀបដែលអ្នកពិនិត្យសិទ្ធិ ឬតម្រង "តើខ្ញុំធ្លាប់ឃើញ ID នេះទេ?" គួរដំណើរការយ៉ាងពិតប្រាកដ។

គំនិតដូចគ្នាពន្យល់ពីអ្នកពិនិត្យស្ទួនពីមុន៖

const small = Array.from({ length: 20_000 }, (_, i) => i);

let t = performance.now();
hasDuplicateSlow(small);
console.log("slow:", (performance.now() - t).toFixed(1), "ms"); // ប្រហែល 75 ms

t = performance.now();
hasDuplicateFast(small);
console.log("fast:", (performance.now() - t).toFixed(2), "ms"); // ប្រហែល 1 ms

ជាមួយ 5,000 ធាតុ តេស្តដូចគ្នាប្រើពេលប្រហែល 4.6 ms សម្រាប់កំណែយឺត។ ជាមួយ 20,000 ធាតុ (ច្រើនជាង 4 ដង) វាប្រើពេលយូរជាងប្រហែល 16 ដង។ នោះគឺ O(n^2) បង្ហាញខ្លួនក្នុងលេខពិត៖ ទិន្នន័យ 4 ដង ពេលវេលា 16 ដង។

12. Linear Search ទល់នឹង Binary Search

ឥឡូវការប្រណាំងដែលយើងបានសន្យា។ យក array តម្រៀបរួចនៃលេខគូមួយលាន ហើយរកធាតុចុងក្រោយ ដោយប្រើ function ទាំងពីរ (ធ្វើម្តងទៀត 100 ដងនីមួយៗដើម្បីឱ្យពេលវេលាអាចវាស់បាន)៖

const sorted = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
const target = sorted[sorted.length - 1];

let start = performance.now();
for (let i = 0; i < 100; i++) linearSearch(sorted, target);
const linearMs = performance.now() - start;

start = performance.now();
for (let i = 0; i < 100; i++) binarySearch(sorted, target);
const binaryMs = performance.now() - start;

console.log("linear:", linearMs.toFixed(2), "ms");  // about 60 ms
console.log("binary:", binaryMs.toFixed(4), "ms");  // about 0.1 ms
console.log("binary is faster:", binaryMs < linearMs); // true

Linear search ធ្វើការប្រៀបធៀបប្រហែលមួយលានដងក្នុងមួយការស្វែងរក ចំណែក binary search ធ្វើ 20។ ទោះបីជា binary search មានកូដស្មុគស្មាញជាងក្នុងមួយជំហាន ភាពខុសគ្នានៃរូបរាងគ្របដណ្តប់វា ហើយពេលវេលាពិតខុសគ្នាពីរបីរយដង។ ដូចរាល់ដង ពេលវេលាពិតប្រាកដប្រែប្រួលតាមម៉ាស៊ីន។

អ្នកអាចរាប់ជំហានដើម្បីឃើញរឿងនេះដោយមិនប្រើនាឡិកាបញ្ឈប់៖

let comparisons = 0;
function countingBinarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    comparisons++;
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

countingBinarySearch(sorted, target);
console.log(comparisons); // 20

ចំណុចចាប់មួយ៖ binary search ត្រូវការទិន្នន័យតម្រៀបរួច។ ការតម្រៀបចំណាយ O(n log n)។ ប្រសិនបើអ្នករកបញ្ជីម្តង linear scan ថោកជាងការតម្រៀបជាមុន។ ប្រសិនបើអ្នករកវារាប់ពាន់ដង សូមតម្រៀបម្តង។

13. Space Complexity

ពេលវេលាមិនមែនជាធនធានតែមួយទេ។ Space complexity ពិពណ៌នាថាកូដរបស់អ្នកត្រូវការ អង្គចងចាំបន្ថែម ប៉ុន្មានពេល input លូតលាស់ ដោយប្រើសញ្ញា Big-O ដូចគ្នា។

សូមកត់សម្គាល់លំនាំក្នុងអ្នកពិនិត្យស្ទួន៖ កំណែលឿនចំណាយអង្គចងចាំ O(n) ដើម្បីសន្សំពេលវេលា។ ការបង្កើនល្បឿនជាច្រើនដំណើរការបែបនេះ (cache គឺជាការដោះដូរដូចគ្នានេះ)។ ការសម្រេចចិត្តអាស្រ័យលើអ្វីដែលខ្វះខាត៖ លើទូរស័ព្ទដែលមានអង្គចងចាំតិច ឬជាមួយសំណុំទិន្នន័យដ៏ធំ អ្នកប្រហែលជាចូលចិត្តកំណែយឺតជាង ប៉ុន្តែស្គម។

14. រូបមន្ត៖ Module bench

បន្ថែមឧបករណ៍របស់ជំពូកនេះទៅ mathlab។ បង្កើត src/bench.js៖

// src/bench.js

// ដំណើរការ fn ម្តង ហើយរាយការណ៍ថាវាប្រើពេលប៉ុន្មាន។
export function time(fn, label = "task") {
  const start = performance.now();
  const result = fn();
  const ms = performance.now() - start;
  return { label, ms, result };
}

// O(n): មើលធាតុម្តងមួយៗ។
export function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// O(log n): array ត្រូវតម្រៀបរួចតាមលំដាប់ឡើងរួចហើយ។
export function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

time(fn, label) ត្រឡប់ object ដែលផ្ទុក label, មីលីវិនាទីដែលបានកន្លងផុត និងអ្វីដែល fn ត្រឡប់ ដូច្នេះអ្នកអាចបោះពុម្ព ឬប្រៀបធៀបវា។ Re-export module ពី src/index.js៖

export * from "./bench.js";

បន្ថែមកូដនេះទៅ demo.js ហើយដំណើរការ node demo.js៖

import { time, linearSearch, binarySearch } from "./src/bench.js";

console.log("--- bench ---");
const sorted = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
const last = sorted[sorted.length - 1];
const set = new Set(sorted);

console.log(linearSearch(sorted, last)); // 999999
console.log(binarySearch(sorted, last)); // 999999
console.log(binarySearch(sorted, 7));    // -1 (7 ជាលេខសេស ដូច្នេះវាមិនមានក្នុងបញ្ជី)

const linear = time(() => {
  for (let i = 0; i < 100; i++) linearSearch(sorted, last);
}, "linear x100");
const binary = time(() => {
  for (let i = 0; i < 100; i++) binarySearch(sorted, last);
}, "binary x100");
const includes = time(() => {
  for (let i = 0; i < 100; i++) sorted.includes(last);
}, "includes x100");
const setHas = time(() => {
  for (let i = 0; i < 100; i++) set.has(last);
}, "set.has x100");

for (const r of [linear, binary, includes, setHas]) {
  console.log(r.label.padEnd(14), r.ms.toFixed(3), "ms"); // ពេលវេលាប្រែប្រួលតាមម៉ាស៊ីន
}
console.log("binary faster than linear:", binary.ms < linear.ms);   // true
console.log("Set.has faster than includes:", setHas.ms < includes.ms); // true

លទ្ធផលស្វែងរកទាំងបី និងបន្ទាត់ true ទាំងពីរមានស្ថេរភាព ចំណែកលេខមីលីវិនាទីមិនស្ថិរភាពទេ។ នៅលើកុំព្យូទ័រយួរដៃមួយ បន្ទាត់ពេលវេលាទាំងបួនចេញមកប្រហែល 62 ms, 0.1 ms, 14 ms និង 0.03 ms។ របស់អ្នកនឹងខុសគ្នា ប៉ុន្តែលំដាប់គួរតែដូចគ្នា។

15. សាកល្បងដោយខ្លួនឯង

1. ចាត់ថ្នាក់ទាំងនេះ។ ផ្តល់ Big-O សម្រាប់នីមួយៗ៖ (a) arr[5]; (b) for loop តែមួយលើ arr; (c) for loop លើ arr ដែលមាន arr.includes(x) នៅខាងក្នុង; (d) while (n > 1) n = n / 2; (e) arr.sort(...); (f) loop ជ្រៅបីជាន់លើ arr។
2. បោះចោលថេរ។ សម្រួល 5n + 20, n^2 + 1000n និង 3 * 2^n + n^5។ តើនីមួយៗសម្រួលទៅជាអ្វី?
3. រាប់ការងារ។ សរសេរ countTriples(n) ជាមួយ loop ជ្រៅបីជាន់ ដែលនីមួយៗពី 0 ដល់ n - 1 ហើយរាប់ចំនួនជុំ។ បោះពុម្ពសម្រាប់ n = 5 និង n = 10។ តើការរាប់កើនឡើងប៉ុន្មានដងពេល n ទ្វេដង?
4. រកចំណុចស្មើគ្នា (break-even)។ វាស់ពេល hasDuplicateSlow និង hasDuplicateFast លើ array នៃលេខខុសៗគ្នា 100, 1,000 និង 10,000 ដោយប្រើ time ពី src/bench.js។ នៅទំហំណាដែលកំណែ Set ឈ្នះយ៉ាងច្បាស់?
5. ជួសជុល loop ដែលលាក់។ អ្នកមាន orders និង customers ដែលនីមួយៗមាន object 1,000។ សរសេរ loop orders ពីផ្នែកទី 5 ឡើងវិញ ដើម្បីឱ្យវាសាងសង់ Map នៃអតិថិជនតាម id ជាមុន។ ពន្យល់ក្នុងប្រយោគមួយថាហេតុអ្វីវាលឿនជាង។
6. ឧបករណ៍រាប់ជំហាន binary search។ កែ binarySearch ឱ្យត្រឡប់ចំនួនការប្រៀបធៀបដែលវាបានធ្វើផងដែរ។ ដំណើរការលើ array នៃធាតុតម្រៀបរួច 10, 1,000 និង 1,000,000 ដោយរកតម្លៃដែលបាត់។ តើការរាប់ត្រូវនឹង Math.ceil(Math.log2(n + 1)) ឬទេ?

ទៅទីណាបន្ត។ Big-O គឺជាវាក្យសព្ទនៃការរចនា algorithm។ ស៊េរី Data Structures & Algorithms ដែលបានគ្រោងទុកនៅលើគេហទំព័រនេះសាងសង់លើវា៖ array ទល់នឹង hash map, linked list, stack, queue, tree, graph, ការតម្រៀប និង recursion ដោយតែងសួរថា "តើតម្លៃប៉ុន្មាន?"។ សម្រាប់ពេលនេះ អ្នកដឹងគ្រប់គ្រាន់ដើម្បីស្គាល់ loop quadratic ក្នុងការត្រួតពិនិត្យកូដ (code review)។

Big-O ឆ្លើយសំណួរ "តើមានការងារប៉ុន្មាន?"។ សំណួរបន្ទាប់គឺ "តើមានលទ្ធភាពប៉ុន្មាន?" ដែលជាកន្លែងដែល combinatorics ចូលមក៖ ការរាប់៖ Permutation និង Combination។