სარჩევი[დამალვა][ჩვენება]
კომპიუტერული მეცნიერება არის ალგორითმების და მონაცემთა სტრუქტურების სირთულეების გაგება.
თქვენ გაქვთ დასალაგებელი ელემენტების სია, მაგრამ არ გაქვთ დრო ან რესურსი უფრო რთული დახარისხების ალგორითმის გამოსაყენებლად.
ჩასმის დახარისხება არის ერთ-ერთი უმარტივესი დახარისხების ალგორითმი, მაგრამ ის შეიძლება იყოს ნელი დიდი სიებისთვის.
მარტივმა განხორციელებამ და გაგებამ ეს მეთოდი პროგრამისტებს შორის ფავორიტად აქცია. ეს შესანიშნავია მცირე სიებისთვის ან როდესაც გჭირდებათ სწრაფი გადაწყვეტა.
ამ ბლოგ პოსტში ჩვენ განვიხილავთ ჩასმის დახარისხების დროის სირთულეს. ეს ალგორითმი გამოიყენება მასივების დასალაგებლად და აქვს O(n2). ეს ნიშნავს, რომ დროის სირთულე იზრდება მასივის ზომასთან ერთად.
თუმცა, ეს ალგორითმი შეიძლება იყოს უფრო ხშირად, ვიდრე სხვა დახარისხების ალგორითმები, როგორიცაა სწრაფი დალაგება.
მოდით უფრო დეტალურად განვიხილოთ, თუ როგორ მუშაობს ჩასმის დახარისხება!
რა არის ჩასმის დახარისხების ალგორითმი?
ერთი ელემენტი ერთდროულად, ჩასმის დალაგება წარმოქმნის დასალაგებელ მასივს, რომელსაც ხშირად უწოდებენ სიას.
მაგალითად, დახარისხება გამოიყენება რთულ კომპიუტერულ პროგრამებში, როგორიცაა შემდგენელები, სადაც ტოკენების თანმიმდევრობა მნიშვნელოვანია პროგრამის ინტერპრეტაციისთვის.
როგორ მუშაობს ჩასმის სორტირება?
როდესაც მასივის დასალაგებლად ვიყენებთ ჩასმის დალაგებას, ალგორითმი იწყება სიაში ყველაზე პატარა ელემენტის მოძიებით და სწორ პოზიციაში ჩასმით.
შემდეგ ის პოულობს შემდეგ უმცირეს ნივთს და აყენებს მას სწორ პოზიციაში და ა.შ.
ალგორითმი მუშაობს სიის მარყუჟის მეშვეობით, თითოეული ელემენტის შედარება წინა პუნქტთან.
თუ ელემენტები არასწორი თანმიმდევრობითაა, ალგორითმი ცვლის მათ. შემდეგ ის ამოწმებს დალაგებულია თუ არა სია და თუ ასეა, ალგორითმი მთავრდება.
პრაქტიკაში, ჩასმის დალაგება ხშირად ხორციელდება კოდის რამდენიმე ხაზის გამოყენებით, რაც მას პოპულარულ არჩევანს ხდის მცირე მასივების დასალაგებლად. თუმცა, ამ ალგორითმის გამოყენებისას გასათვალისწინებელია დროის სირთულე.
მაგალითი:
აქ არის მაგალითი იმისა, თუ როგორ მუშაობს ჩასმის დახარისხება. ჩვენ გამოვიყენებთ შემდეგ მასივს:
1, 2, 3, 4, 5, 6
ალგორითმი იწყება სიაში ყველაზე პატარა ელემენტის მოძიებით, რომელიც არის 1. შემდეგ ის ჩასვით სწორ პოზიციაზე, პირველ პოზიციაზე. შემდეგ ის პოულობს შემდეგ უმცირეს ერთეულს, რომელიც არის 2. ის აყენებს მას სწორ პოზიციაში, რომელიც არის მეორე პოზიცია.
შემდეგ ის პოულობს შემდეგ უმცირეს ერთეულს, რომელიც არის 3. ის აყენებს მას სწორ პოზიციაში, რომელიც არის მესამე პოზიცია.
შემდეგ ის პოულობს შემდეგ უმცირეს ერთეულს, რომელიც არის 4. ის აყენებს მას სწორ პოზიციაში, რომელიც არის მეოთხე პოზიცია და ა.შ. სია ახლა დალაგებულია!
მაგალითიდან ვხედავთ, რომ ალგორითმი იღებს ექვს შედარებას და ცვლას სიის დასალაგებლად. ეს იმიტომ ხდება, რომ სჭირდება ნ2 შედარება და გაცვლა n ელემენტის სიის დასალაგებლად. ამ შემთხვევაში n=6.
როგორ გავაუმჯობესოთ ჩასმის დახარისხების დროის სირთულე?
მიუხედავად იმისა, რომ ჩასმის დალაგება აქვს O(n2), ის შეიძლება გაუმჯობესდეს უკეთესი დახარისხების ალგორითმის გამოყენებით, როგორიცაა სწრაფი დახარისხება.
Quicksort-ს აქვს O(n log n) გაშვების დრო, რაც ბევრად უფრო სწრაფია ვიდრე O(n2).
თუმცა, ზოგიერთ შემთხვევაში, ჩასმის დახარისხება შეიძლება იყოს უფრო სწრაფი, ვიდრე სწრაფი.
მაგალითად, თუ სია უკვე წესრიგშია, ჩასმის დახარისხებას ნაკლები დრო დასჭირდება, ვიდრე სწრაფი დახარისხება.
პრაქტიკაში, ჩასმის დალაგება ხშირად ხორციელდება კოდის რამდენიმე ხაზის გამოყენებით, რაც მას პოპულარულ არჩევანს ხდის მცირე მასივების დასალაგებლად.
თუმცა, ამ ალგორითმის გამოყენებისას გასათვალისწინებელია დროის სირთულე.
დროის სირთულეები
ყველაზე ცუდი შემთხვევის სირთულე O(n2):
დროის სირთულე იზრდება მასივის ზომასთან ერთად. სჭირდება ნ2 შედარება და გაცვლა n ელემენტის სიის დასალაგებლად.
მაგალითად, თუ გვაქვს 1000 ზომის მასივი, ალგორითმი დასჭირდება 1,000,000 შედარებას და სვოპს მასივის დასალაგებლად.
საუკეთესო საქმის სირთულე O(n):
დროის სირთულე იგივეა, რაც შეყვანის მასივის ზომა. მე
t იღებს n შედარებას და ცვლის n ელემენტის სიის დასალაგებლად. მაგალითად, განიხილეთ 5 ზომის მასივი. ალგორითმი დასჭირდება ხუთ შედარებას და გაცვლას მასივის დასალაგებლად.
საქმეების საშუალო სირთულე O(n2):
დროის სირთულე ამ შემთხვევაში არის ყველაზე ცუდ და საუკეთესო შემთხვევის სირთულეებს შორის.
სჭირდება ნ2 შედარება და გაცვლა n ელემენტის სიის დასალაგებლად.
ამრიგად, ჩასმის დახარისხება არის სტაბილური დახარისხების ალგორითმი.
რატომ არის ჩასმის დახარისხება სტაბილური?
ჩასმის დალაგება სტაბილურია, რადგან ის ინარჩუნებს თანაბარ ელემენტებს შეყვანის მასივში.
ეს მნიშვნელოვანია მრავალი აპლიკაციისთვის, როგორიცაა მონაცემთა მოძიება ან ფინანსური ანალიზი. მაგალითად, თუ გვაქვს რიცხვების ორი სია და გვინდა შევადაროთ ისინი, უნდა დავრწმუნდეთ, რომ ელემენტების თანმიმდევრობა დაცულია.
თუ სიები არ არის დალაგებული, ჩვენ მათ ზუსტად არ შევადარებთ.
დატოვე პასუხი