1.ในการนับเพื่อเพิ่มค่าของหลุม(holes) จะทำเท่ากับสมาชิกของอเรย์ หากให้สมาชิกของอเรย์เท่ากับ n จะได้ O(n)
2.ในการนับเพื่อที่จะเขียนทับไปยังอเรย์เดิมจะทำเท่ากับจำนวนของสมาชิกใน size ซึ่งมากจาก ค่าสูงสุดของอเรย์-ค่าต่ำสุดของอเรย์ +1 กำหนดให้เป็น m และเงื่อนไงของการที่จะเขียนทับลงไปยังอเรย์เดิมคืออเรย์ที่ holes ใดๆ ต้องมากกว่า 0 กำหนดให้เป็น x ดังนั้นสรุปได้ว่าความซับซ้อนจะมีค่าเป็น O(mx)
3.ดังนั้นเราสามารถสรุปได้ว่าขั้นตอนความซับซ้อนของการเรียงลำดับนี้คือ O(n+mx) ซึ่ง n=x เนื่องจากจากเงื่อนไงของ x มาจากจำนวนของ n ดังนั้นความซับซ้อนเท่ากับO(n+mn) เมื่อให้ N = mn จะได้ความซับซ้อนของขั้นตอนวิธี O(n+N)
การเร, ยงลำด, บแบบร, งนกพ, ราบ, งกฤษ, pigeonhole, sorting, เป, นข, นตอนว, การเร, ยงลำด, บท, เหมาะก, บการเร, ยงลำด, บรายการส, วนย, อยท, จำนวนส, วนย, อย, และความยาวของพ, ยค, าหล, กท, เป, นไปได, ประมาณเท, องใช, คร, การเร, ยงลำด, บแบบน, คล, ายก, บการเร, ยงลำด, บน,. kareriyngladbaebbrngnkphirab xngkvs pigeonhole sorting epnkhntxnwithikareriyngladbthiehmaakbkareriyngladbraykarswnyxythicanwnswnyxy n aelakhwamyawkhxngphisykhahlkthiepnipid N pramanetha kn txngich O n N khrng kareriyngladbaebbnikhlaykbkareriyngladbnb aettangknthikareriyngladbni yayraykarsxngkhrng khrnghnungekhaaethwladbthifakkhxmulaelwxikkhrngyaykbcudhmaysudthay enuxha 1 karthangankhxngkareriyngladb 2 karwiekhraahkhwamsbsxnkhxngkhntxnwithi 3 CODE PYTHON 4 TEST CASEkarthangankhxngkareriyngladb aekikh kahndihepn array khxngkhathicaeriyngladb odykahnd array thicachwyinkareriyngladb array michuxwa holes sungepn array wangeplathirxrbcanwnsmachikepnchwngkhxng array edim thi array thitxngkarcderiyngeraiskhaaetla array lngin holes thitrngkbtaaehnngkhxng array edim thasain holes odyekhiynthb array edimtamxngkhprakxbkhxng holes waxyutaaehnngihnbangkarwiekhraahkhwamsbsxnkhxngkhntxnwithi aekikh1 inkarnbephuxephimkhakhxnghlum holes cathaethakbsmachikkhxngxery hakihsmachikkhxngxeryethakb n caid O n 2 inkarnbephuxthicaekhiynthbipyngxeryedimcathaethakbcanwnkhxngsmachikin size sungmakcak khasungsudkhxngxery khatasudkhxngxery 1 kahndihepn m aelaenguxningkhxngkarthicaekhiynthblngipyngxeryedimkhuxxerythi holes id txngmakkwa 0 kahndihepn x dngnnsrupidwakhwamsbsxncamikhaepn O mx 3 dngnnerasamarthsrupidwakhntxnkhwamsbsxnkhxngkareriyngladbnikhux O n mx sung n x enuxngcakcakenguxningkhxng x macakcanwnkhxng n dngnnkhwamsbsxnethakbO n mn emuxih N mn caidkhwamsbsxnkhxngkhntxnwithi O n N 4 inkrnithikhxngmulmikhahemuxnkncasngphlih max min 1 mikhaethakb 1 aelakhwamsbsxnkhxng m 1 caidkhwamsbsxnkhxngkhntxnwithiethakb O n n hrux O 2n nnexngCODE PYTHON aekikhdef Pigeonhole sort array min arr min array size max array min arr 1 holes 0 size for i in array holes i min arr 1 i array 0 for count in range size while holes count gt 0 array i array count min arr holes count 1 i array 1 return arrayTEST CASE aekikhimport unittest from PigeonholeSorting import Pigeonhole sort import random def is sorted array n len array for i in range 1 n if array i lt array i 1 return False return True class test sorting unittest TestCase def test ipigeonhole sort self max size 1500 for size in range 1 max size 1 array random randrange 20 for num in range size sorted Pigeonhole sort array self assertTrue is sorted sorted ekhathungcak https th wikipedia org w index php title kareriyngladbaebbrngnkphirab amp oldid 7605820, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,