មាតិកា[លាក់][បង្ហាញ]
វិទ្យាសាស្ត្រកុំព្យូទ័រគឺនិយាយអំពីការស្វែងយល់ពីភាពស្មុគស្មាញនៃក្បួនដោះស្រាយ និងរចនាសម្ព័ន្ធទិន្នន័យ។
អ្នកមានបញ្ជីធាតុដែលត្រូវតម្រៀប ប៉ុន្តែអ្នកមិនមានពេលវេលា ឬធនធានដើម្បីប្រើក្បួនដោះស្រាយការតម្រៀបដែលស្មុគស្មាញជាងនេះទេ។
ការតម្រៀបបញ្ចូលគឺជាក្បួនដោះស្រាយការតម្រៀបសាមញ្ញបំផុតមួយ ប៉ុន្តែវាអាចយឺតសម្រាប់បញ្ជីធំ។
ការអនុវត្តងាយស្រួល និងការយល់ដឹងបានធ្វើឱ្យវិធីសាស្ត្រនេះក្លាយជាការពេញនិយមក្នុងចំណោមអ្នកសរសេរកម្មវិធី។ វាល្អឥតខ្ចោះសម្រាប់បញ្ជីតូចៗ ឬនៅពេលដែលអ្នកត្រូវការដំណោះស្រាយរហ័ស។
នៅក្នុងការប្រកាសប្លក់នេះ យើងនឹងពិនិត្យមើលភាពស្មុគស្មាញនៃពេលវេលានៃការតម្រៀបការបញ្ចូល។ ក្បួនដោះស្រាយនេះត្រូវបានប្រើដើម្បីតម្រៀបអារេ ហើយវាមានពេលដំណើរការ O(n2) នេះមានន័យថាភាពស្មុគស្មាញនៃពេលវេលាកើនឡើងជាមួយនឹងទំហំនៃអារេ។
ទោះយ៉ាងណាក៏ដោយ ក្បួនដោះស្រាយនេះអាចលឿនជាងក្បួនដោះស្រាយការតម្រៀបផ្សេងទៀត ដូចជាការតម្រៀបរហ័ស។
ចូរយើងពិនិត្យមើលឱ្យកាន់តែច្បាស់អំពីរបៀបដែលការតម្រៀបការបញ្ចូលដំណើរការ!
អ្វីទៅជា Insertion Sort Algorithm?
ធាតុមួយក្នុងពេលតែមួយ ការដាក់បញ្ចូលបង្កើតអារេដែលអាចតម្រៀបបាន ដែលជារឿយៗត្រូវបានគេហៅថាបញ្ជី។
ឧទាហរណ៍ ការតម្រៀបត្រូវបានអនុវត្តនៅក្នុងកម្មវិធីកុំព្យូទ័រដ៏ស្មុគស្មាញ ដូចជាកម្មវិធីចងក្រង ដែលលំដាប់នៃសញ្ញាសម្ងាត់មានសារៈសំខាន់ចំពោះការបកស្រាយនៃកម្មវិធី។
តើការតម្រៀបការបញ្ចូលដំណើរការយ៉ាងដូចម្តេច?
នៅពេលយើងប្រើការតម្រៀបការបញ្ចូលដើម្បីតម្រៀបអារេមួយ ក្បួនដោះស្រាយចាប់ផ្តើមដោយការស្វែងរកធាតុតូចបំផុតក្នុងបញ្ជី ហើយបញ្ចូលវាទៅក្នុងទីតាំងត្រឹមត្រូវ។
បន្ទាប់មកវាស្វែងរកធាតុតូចបំផុតបន្ទាប់ ហើយបញ្ចូលវាទៅក្នុងទីតាំងត្រឹមត្រូវ ហើយដូច្នេះនៅលើ។
ក្បួនដោះស្រាយដំណើរការដោយរង្វិលជុំតាមបញ្ជី ដោយប្រៀបធៀបធាតុនីមួយៗទៅនឹងធាតុដែលមកមុនវា។
ប្រសិនបើធាតុស្ថិតក្នុងលំដាប់ខុស ក្បួនដោះស្រាយនឹងប្តូរពួកវា។ បន្ទាប់មកវាពិនិត្យដើម្បីមើលថាតើបញ្ជីត្រូវបានតម្រៀប ហើយប្រសិនបើវាជា នោះក្បួនដោះស្រាយបញ្ចប់។
នៅក្នុងការអនុវត្ត ការតម្រៀបការបញ្ចូលត្រូវបានអនុវត្តជាញឹកញាប់ដោយប្រើបន្ទាត់មួយចំនួននៃកូដ ដែលធ្វើឱ្យវាក្លាយជាជម្រើសដ៏ពេញនិយមសម្រាប់តម្រៀបអារេតូច។ ទោះជាយ៉ាងណាក៏ដោយភាពស្មុគស្មាញនៃពេលវេលាគួរតែត្រូវបានពិចារណានៅពេលប្រើក្បួនដោះស្រាយនេះ។
ឧទាហរណ៍:
នេះគឺជាឧទាហរណ៍អំពីរបៀបដែលការតម្រៀបបញ្ចូលដំណើរការ យើងនឹងប្រើអារេខាងក្រោម៖
1, 2, 3, 4, 5, 6
ក្បួនដោះស្រាយចាប់ផ្តើមដោយការស្វែងរកធាតុតូចបំផុតក្នុងបញ្ជីគឺ 1. បន្ទាប់មកបញ្ចូលវាទៅក្នុងទីតាំងត្រឹមត្រូវ ទីតាំងទីមួយ។ បន្ទាប់មកវារកឃើញធាតុតូចបំផុតបន្ទាប់គឺ 2. វាបញ្ចូលវាទៅក្នុងទីតាំងត្រឹមត្រូវដែលជាទីតាំងទីពីរ។
បន្ទាប់មកវារកឃើញធាតុតូចបំផុតបន្ទាប់គឺ 3. វាបញ្ចូលវាទៅក្នុងទីតាំងត្រឹមត្រូវដែលជាទីតាំងទីបី។
បន្ទាប់មកវារកឃើញធាតុតូចបំផុតបន្ទាប់គឺ 4. វាបញ្ចូលវាទៅក្នុងទីតាំងត្រឹមត្រូវដែលជាទីតាំងទី XNUMX ហើយដូច្នេះនៅលើ។ ឥឡូវនេះបញ្ជីត្រូវបានតម្រៀបហើយ!
យើងអាចមើលឃើញពីឧទាហរណ៍ដែលក្បួនដោះស្រាយយកការប្រៀបធៀបនិងការប្ដូរចំនួនប្រាំមួយដើម្បីតម្រៀបបញ្ជី។ នេះគឺដោយសារតែវាយក n2 ការប្រៀបធៀប និងការផ្លាស់ប្តូរដើម្បីតម្រៀបបញ្ជីនៃធាតុ n ។ ក្នុងករណីនេះ n=6 ។
តើធ្វើដូចម្តេចដើម្បីកែលម្អភាពស្មុគស្មាញនៃពេលវេលាតម្រៀបបញ្ចូល?
ខណៈពេលដែលការតម្រៀបបញ្ចូលមានពេលវេលារត់នៃ O(n2) វាអាចត្រូវបានធ្វើឱ្យប្រសើរឡើងដោយការប្រើក្បួនដោះស្រាយការតម្រៀបល្អប្រសើរជាងមុនដូចជាការតម្រៀបរហ័ស។
Quicksort មានពេលវេលាដំណើរការ O(n log n) ដែលលឿនជាង O(n2).
ទោះយ៉ាងណាក៏ដោយ ក្នុងករណីខ្លះ ការតម្រៀបបញ្ចូលអាចលឿនជាងការតម្រៀបរហ័ស។
ឧទាហរណ៍ ប្រសិនបើបញ្ជីស្ថិតក្នុងលំដាប់រួចហើយ ការតម្រៀបការបញ្ចូលនឹងចំណាយពេលតិចជាងការតម្រៀបរហ័ស។
នៅក្នុងការអនុវត្ត ការតម្រៀបការបញ្ចូលត្រូវបានអនុវត្តជាញឹកញាប់ដោយប្រើបន្ទាត់មួយចំនួននៃកូដ ដែលធ្វើឱ្យវាក្លាយជាជម្រើសដ៏ពេញនិយមសម្រាប់តម្រៀបអារេតូច។
ទោះជាយ៉ាងណាក៏ដោយភាពស្មុគស្មាញនៃពេលវេលាគួរតែត្រូវបានពិចារណានៅពេលប្រើក្បួនដោះស្រាយនេះ។
ភាពស្មុគស្មាញនៃពេលវេលា
ករណីដ៏អាក្រក់បំផុត ភាពស្មុគស្មាញ O(n2):
ភាពស្មុគស្មាញនៃពេលវេលាកើនឡើងជាមួយនឹងទំហំនៃអារេ។ វាត្រូវការ n2 ការប្រៀបធៀប និងការផ្លាស់ប្តូរដើម្បីតម្រៀបបញ្ជីនៃធាតុ n ។
ឧទាហរណ៍ ប្រសិនបើយើងមានអារេនៃទំហំ 1000 នោះក្បួនដោះស្រាយនឹងយក 1,000,000 ការប្រៀបធៀប និងការផ្លាស់ប្តូរដើម្បីតម្រៀបអារេ។
ភាពស្មុគស្មាញនៃករណីល្អបំផុត O(n)៖
ភាពស្មុគស្មាញនៃពេលវេលាគឺដូចគ្នាទៅនឹងទំហំនៃអារេបញ្ចូល។ ខ្ញុំ
t យក n ការប្រៀបធៀប និង swaps ដើម្បីតម្រៀបបញ្ជីរបស់ n ។ ជាឧទាហរណ៍ សូមពិចារណាអារេនៃទំហំ 5 ។ ក្បួនដោះស្រាយនឹងយកការប្រៀបធៀបចំនួនប្រាំ និងការផ្លាស់ប្តូរដើម្បីតម្រៀបអារេ។
ភាពស្មុគស្មាញករណីជាមធ្យម O(n2):
ភាពស្មុគស្មាញនៃពេលវេលាគឺរវាងភាពស្មុគស្មាញករណីអាក្រក់បំផុត និងល្អបំផុតក្នុងករណីនេះ។
វាត្រូវការ n2 ការប្រៀបធៀប និងការផ្លាស់ប្តូរដើម្បីតម្រៀបបញ្ជីនៃធាតុ n ។
ដូច្នេះការតម្រៀបបញ្ចូលគឺជាក្បួនដោះស្រាយការតម្រៀបមានស្ថិរភាព។
ហេតុអ្វីបានជាការតម្រៀបបញ្ចូលមានស្ថេរភាព?
ការតម្រៀបការបញ្ចូលមានស្ថិរភាពដោយសារវារក្សាលំដាប់នៃធាតុស្មើគ្នាក្នុងអារេបញ្ចូល។
នេះមានសារៈសំខាន់សម្រាប់កម្មវិធីជាច្រើន ដូចជាការទាញយកទិន្នន័យ ឬការវិភាគហិរញ្ញវត្ថុជាដើម។ ឧទាហរណ៍ ប្រសិនបើយើងមានបញ្ជីលេខពីរ ហើយចង់ប្រៀបធៀបពួកវា យើងត្រូវធ្វើឱ្យប្រាកដថា លំដាប់នៃធាតុត្រូវបានរក្សាទុក។
ប្រសិនបើបញ្ជីមិនត្រូវបានតម្រៀបទេ យើងនឹងមិនប្រៀបធៀបពួកវាឱ្យបានត្រឹមត្រូវទេ។
សូមផ្ដល់យោបល់