د کمپیوټر ساینس ټول د الګوریتمونو او ډیټا جوړښتونو پیچلتیاو پوهیدو په اړه دي.
تاسو د توکو لیست لرئ چې ترتیب ته اړتیا لري، مګر تاسو د ډیر پیچلي ترتیب کولو الګوریتم کارولو لپاره وخت یا سرچینې نلرئ.
د داخلولو ترتیب کول یو له ساده ترتیب کولو الګوریتمونو څخه دی، مګر دا د لوی لیستونو لپاره ورو کیدی شي.
اسانه پلي کول او پوهه دا طریقه د پروګرام کونکو تر مینځ غوره کړې. دا د کوچنیو لیستونو لپاره مناسب دی یا کله چې تاسو چټک حل ته اړتیا لرئ.
پدې بلاګ پوسټ کې ، موږ به د ننوتلو ترتیب کولو وخت پیچلتیا وګورو. دا الګوریتم د صفونو ترتیب کولو لپاره کارول کیږي، او دا د O(n2). دا پدې مانا ده چې د وخت پیچلتیا د سرې اندازې سره وده کوي.
په هرصورت، دا الګوریتم اکثرا د نورو ترتیب کولو الګوریتمونو په پرتله ګړندی کیدی شي، لکه Quicksort.
راځئ چې نږدې وګورو چې څنګه د ننوتلو ترتیب کول کار کوي!
د داخلولو ترتیب الګوریتم څه شی دی؟
په یو وخت کې یو عنصر، د ننوتلو ترتیب د ترتیب کولو وړ سرې رامینځته کوي، کوم چې ډیری وختونه د لیست په توګه ویل کیږي.
د مثال په توګه، ترتیب کول د کمپیوټر په پیچلو پروګرامونو لکه کمپیلرونو کې پلي کیږي، چیرته چې د توکیو ترتیب د پروګرام تفسیر لپاره مهم دی.
د داخلولو ترتیب څنګه کار کوي؟
کله چې موږ د سري ترتیب کولو لپاره د داخل کولو ډول کاروو، الګوریتم په لیست کې د کوچني توکي موندلو او سم موقعیت ته د ننوتلو سره پیل کیږي.
دا بیا راتلونکی کوچنی توکي پیدا کوي او سم موقعیت ته یې داخلوي، او داسې نور.
الګوریتم د لیست له لارې د لوپ کولو سره کار کوي، هر توکي د هغه سره پرتله کوي چې مخکې راځي.
که توکي په غلط ترتیب کې وي، الګوریتم دوی بدلوي. دا بیا ګوري چې ایا لیست ترتیب شوی، او که دا وي، الګوریتم پای ته رسیږي.
په عمل کې، د ننوتلو ترتیب اکثرا د کوډ د څو لینونو په کارولو سره پلي کیږي، دا د کوچنیو صفونو ترتیب کولو لپاره یو مشهور انتخاب جوړوي. په هرصورت، د دې الګوریتم کارولو په وخت کې د وخت پیچلتیا باید په پام کې ونیول شي.
مثال:
دلته یو مثال دی چې څنګه د ننوتلو ترتیب کول کار کوي. موږ به لاندې صفونه وکاروو:
1، 2، 3، 4، 5، 6
الګوریتم په لیست کې د ترټولو کوچني توکي موندلو سره پیل کیږي، کوم چې 1 دی. بیا یې سم موقعیت ته داخلوي، لومړی ځای. دا بیا بل کوچنی توکی پیدا کوي، کوم چې 2 دی. دا سم موقعیت ته داخلوي، کوم چې دویم ځای دی.
دا بیا بل کوچنی توکی پیدا کوي، کوم چې 3 دی. دا سم موقعیت ته داخلوي، کوم چې دریم ځای دی.
دا بیا بل کوچنی توکی پیدا کوي، کوم چې 4 دی. دا سم موقعیت ته داخلوي، کوم چې څلورم ځای دی، او داسې نور. لیست اوس ترتیب شوی!
موږ کولی شو د مثال څخه وګورو چې الګوریتم د لیست ترتیب کولو لپاره شپږ پرتله کول او بدلونونه اخلي. دا ځکه چې دا n اخلي2 د n توکو لیست ترتیبولو لپاره پرتله کول او تبادله. په دې حالت کې، n = 6.
څنګه د داخلولو ترتیب وخت پیچلتیا ښه کړو؟
پداسې حال کې چې د ننوتلو ترتیب د O(n2)، دا د غوره ترتیب کولو الګوریتم په کارولو سره ښه کیدی شي، لکه quicksort.
Quicksort د O (n log n) رن ټایم لري، کوم چې د O (n) په پرتله خورا ګړندی دی2).
په هرصورت، په ځینو حاالتو کې، د ننوتلو ترتیب کول د چټک ترتیب په پرتله ګړندي کیدی شي.
د مثال په توګه، که لیست دمخه په ترتیب کې وي، د داخلولو ترتیب کول به د Quicksort په پرتله لږ وخت ونیسي.
په عمل کې، د ننوتلو ترتیب اکثرا د کوډ د څو لینونو په کارولو سره پلي کیږي، دا د کوچنیو صفونو ترتیب کولو لپاره یو مشهور انتخاب جوړوي.
په هرصورت، د دې الګوریتم کارولو په وخت کې د وخت پیچلتیا باید په پام کې ونیول شي.
د وخت پیچلتیاوې
د بدترین قضیې پیچلتیا O(n2):
د وخت پیچلتیا د صف اندازې سره ډیریږي. دا n اخلي2 د n توکو لیست ترتیبولو لپاره پرتله کول او تبادله.
د مثال په توګه، که موږ د 1000 اندازه اندازه ولرو، الګوریتم به 1,000,000 پرتله کړي او د صف ترتیبولو لپاره بدل کړي.
د غوره قضیې پیچلتیا O(n):
د وخت پیچلتیا د ان پټ سرې اندازې سره ورته ده. زه
t د n توکو لیست ترتیبولو لپاره n پرتله کول او تبادله کوي. د مثال په توګه، د 5 اندازه اندازه په پام کې ونیسئ. الګوریتم به پنځه پرتله کولو او تبادلو ته اړتیا ولري ترڅو د ترتیب ترتیب کړي.
د اوسط قضیې پیچلتیا O(n2):
د وخت پیچلتیا پدې قضیه کې د بدترین او غوره قضیې پیچلتیاو ترمنځ ده.
دا n اخلي2 د n توکو لیست ترتیبولو لپاره پرتله کول او تبادله.
په دې توګه، د ننوتلو ترتیب کول یو مستحکم ترتیب الګوریتم دی.
ولې د ننوتلو ترتیب مستحکم دی؟
د ننوتلو ترتیب مستحکم دی ځکه چې دا د ان پټ سري کې د مساوي عناصرو ترتیب ساتي.
دا د ډیری غوښتنلیکونو لپاره مهم دی، لکه د معلوماتو ترلاسه کول یا مالي تحلیل. د مثال په توګه، که موږ د شمیرو دوه لیستونه لرو او غواړو چې دوی پرتله کړو، موږ باید ډاډ ترلاسه کړو چې د عناصرو ترتیب ساتل کیږي.
که لیستونه ترتیب نه وي، موږ به یې په سمه توګه پرتله نه کړو.
یو ځواب ورکړئ ووځي