[Powered by Google Translate] თქვენ ალბათ მსმენია ადამიანები საუბრობენ სწრაფად ან ეფექტური ალგორითმი ამისთვის შესრულებაში თქვენი კონკრეტული ამოცანა, მაგრამ რას ნიშნავს ეს შეეხება ალგორითმი უნდა იყოს სწრაფი ან ეფექტური? ისე, ეს არ ვსაუბრობთ გაზომვა რეალურ დროში, მოსწონს წამში ან წუთში. ეს იმიტომ კომპიუტერული ტექნიკა და პროგრამული უზრუნველყოფის განსხვავდება რადიკალურად. ჩემი პროგრამა შეიძლება აწარმოებს ნელია ვიდრე შენია, რადგან მე გაშვებული ეს ხანდაზმული კომპიუტერი, ან იმიტომ, რომ მე არ უნდა იყოს თამაშობენ ონლაინ ვიდეო თამაში ამავე დროს, რომელიც hogging ყველა ჩემს მეხსიერებას, ან მე შეიძლება გაშვებული ჩემი პროგრამის მეშვეობით სხვადასხვა პროგრამული რაც ურთიერთობა მანქანა განსხვავებულად დაბალ დონეზე. ეს იგივეა, თითქოს შედარებით ვაშლი და ფორთოხალი. მხოლოდ იმიტომ, რომ ჩემი ნელი კომპიუტერი იღებს აღარ ვიდრე შენია მისცეს უკან პასუხი არ ნიშნავს, თქვენ გაქვთ უფრო ეფექტური ალგორითმი. 

ასე რომ, რადგან ჩვენ არ შეგვიძლია პირდაპირ შედარების runtimes პროგრამების წამებში ან წუთის, როგორ შევადარებთ 2 სხვადასხვა ალგორითმები მიუხედავად მათი პროგრამასა თუ გარემო? უფრო ერთგვაროვან გზა საზომი ალგორითმული ეფექტურობის, კომპიუტერის მეცნიერები და მათემატიკოსები არ შეიმუშავეს კონცეფციები საზომი asymptotic სირთულის პროგრამის და ნოტაცია სახელად "დიდი Ohnotation ' აღწერისას ამ. ფორმალური განმარტება ის არის, რომ ფუნქცია f (x) ეშვება ბრძანებით გ (x) თუ არსებობს გარკვეული (x) ღირებულების, x ₀ და ზოგიერთი მუდმივი, C, რისთვისაც f (x) ნაკლებია ან ტოლი რომ მუდმივი ჯერ გ (x) ყველა x მეტია x ₀. 

მაგრამ არ უნდა შეშინებულია სავალია ფორმალური განსაზღვრება. რას ნიშნავს სინამდვილეში ნაკლებად თეორიული თვალსაზრისით? ისე, ეს ძირითადად გზა ანალიზი რამდენად სწრაფად პროგრამის Runtime იზრდება asymptotically. ანუ, როგორც ზომა თქვენი საშუალებებით ზრდის მიმართ Infinity, აცხადებენ, თქვენ დახარისხება მასივი ზომა 1000 წელთან შედარებით მასივი ზომა 10. როგორ ამჯამად Runtime თქვენი პროგრამის იზრდება? მაგალითად, წარმოიდგინეთ დათვლის რაოდენობის სიმბოლოებს in string უმარტივესი გზა  ფეხით მთელ string წერილში-ს წერილი და დასძინა, რომ 1 Counter თითოეული ხასიათი. ეს ალგორითმი განაცხადა გასაშვებად წელს ხაზოვანი დრო მიმართ რაოდენობის სიმბოლოებს, 'N' in string. მოკლედ, ეშვება O (N). რატომ არის ეს? ისე, გამოყენებით ეს მიდგომა, საჭირო დრო to traverse მთელი სიმებიანი პროპორციულია რაოდენობის სიმბოლოებს. დათვლა ხმების სიმბოლოების 20-ხასიათი სიმებიანი აპირებს მიიღოს ორჯერ სანამ ის იღებს დათვლა სიმბოლოების 10-ხასიათის ტექსტი, იმიტომ, რომ თქვენ უნდა შევხედოთ ყველა გმირები და თითოეული ხასიათი იღებს იმავე დროის შევხედოთ. როგორც თქვენ რაოდენობის გაზრდა გმირები, Runtime გაიზრდება ხაზოვანი ერთად შეყვანის სიგრძე. 

ახლა, წარმოიდგინეთ, თუ თქვენ გადაწყვიტავთ, რომ წრფივი დრო, O (N), უბრალოდ არ იყო სწრაფი საკმარისი თქვენთვის? იქნებ თქვენ შენახვა უზარმაზარ სიმები, და თქვენ ვერ მისცემს დამატებით დროში დასჭირდება to traverse ყველა მათი გმირები დათვლის-ს ერთი. ასე რომ, თქვენ გადაწყვიტეთ ძიებასა სხვადასხვა. რა თუ მოხდებოდა უკვე შესანახად რაოდენობის სიმბოლოებს in string, თქმით, იმ ცვლადში 'Len,' დილით პროგრამაში, სანამ კი ინახება პირველივე ხასიათი თქვენს სიმებიანი? მაშინ, ყველა ნეტავ უნდა გავაკეთოთ ახლა გასარკვევად სიმებიანი სიგრძე, არის შეამოწმოს რა ღირებულება ცვლადი. თქვენ არ უნდა შევხედოთ სიმებიანი თავად ყველა, და წვდომის ღირებულება ცვლადი, როგორიცაა len ითვლება asymptotically მუდმივი დრო ოპერაცია, ან O (1). რატომ არის ეს? ისე, გახსოვთ რა asymptotic სირთულის ნიშნავს. როგორ Runtime ენის, როგორც ზომა თქვენი საშუალებებით იზრდება? 

Say You ცდილობდნენ ხმების სიმბოლოების უფრო დიდი სიმებიანი. ასევე, ის არ აქვს მნიშვნელობა რამდენად დიდი თქვენ ტექსტი, თუნდაც მილიონ სიმბოლომდე ყველა ნეტავ უნდა გავაკეთოთ, რათა იპოვოს სიმებიანი მისი სიგრძე ამ მიდგომას, არის წაიკითხა ღირებულება ცვლადი Len, რაც თქვენ უკვე გააკეთა. შეყვანის სიგრძე, რომ არის, სიგრძით string თქვენ ცდილობს იპოვოს, გავლენას არ ახდენს საერთოდ რამდენად სწრაფად თქვენი პროგრამა ეშვება. ეს ნაწილი თქვენს პროგრამაში მიიღებს მონაწილეობას არჩევნებში თანაბრად სწრაფი ერთი ხასიათი სიმებიანი და ათასი სიმბოლოიანი სტრიქონით, და ამიტომაც ეს პროგრამა იქნება მოხსენიებული, როგორც გაშვებული მუდმივი დრო მიმართ შეყვანის ზომა. 

რა თქმა უნდა, არსებობს პრობლემა. თქვენ ხარჯავთ დამატებითი მეხსიერების სივრცე თქვენს კომპიუტერში შენახვის ცვლადი და დამატებითი დრო სჭირდება თქვენ გავაკეთოთ ფაქტობრივი შენახვა ცვლადი, მაგრამ ქულა მაინც დგას, მოძიებაში out რამდენ ხანს თქვენი სიმებიანი იყო არ არის დამოკიდებული სიგრძეზე სიმებიანი ყველა. ასე რომ, იგი ეშვება O (1) ან მუდმივი დრო. ეს, რა თქმა უნდა არ უნდა ნიშნავდეს რომ თქვენი კოდი ეშვება 1 ნაბიჯი, მაგრამ რაც არ უნდა ბევრი ის ნაბიჯი, არის, თუ იგი არ ცვლის იმ ზომის საშუალებებით, მაინც asymptotically მუდმივი რომელსაც ჩვენ წარმოვადგენთ როგორც O (1). 

როგორც თქვენ ალბათ შეუძლია გამოიცნოს, არსებობს მრავალი განსხვავებული დიდი O runtimes საშუალებას გავზომოთ ალგორითმები ერთად. O (N) ² ალგორითმები asymptotically ნელია ვიდრე O (N) ალგორითმები. ანუ, როგორც რაოდენობის ელემენტები (ო) იზრდება, საბოლოოდ O (N) ² ალგორითმები მიიღებს მეტ დროს ვიდრე O (N) ალგორითმები გასაშვებად. ეს არ ნიშნავს, O (N) ალგორითმები ყოველთვის აწარმოებს უფრო სწრაფად ვიდრე O (N) ² ალგორითმები, თუნდაც ერთი და იმავე გარემოში, იმავე აპარატურა. იქნებ მცირე შეყვანის ზომის,  O (N) ² ალგორითმი შეიძლება რეალურად მუშაობა უფრო სწრაფად, მაგრამ, საბოლოო ჯამში, როგორც შეყვანის ზომა იზრდება მიმართ Infinity, O (N) ² ალგორითმი ს runtime საბოლოოდ Eclipse Runtime of O (N) ალგორითმი. ისევე როგორც კვადრატული მათემატიკური ფუნქცია  საბოლოოდ overtake ნებისმიერი წრფივი ფუნქცია, არ აქვს მნიშვნელობა რამდენად ხელმძღვანელი დაიწყოს ხაზოვანი ფუნქცია იწყება off ერთად. თუ თქვენ მუშაობის დიდი რაოდენობით მონაცემები, ალგორითმები, რომ აწარმოებს O (N) ² ახლა ნამდვილად დასრულდება მდე შენელებისა თქვენი პროგრამა, მაგრამ მცირე ზომის შეყვანის, თქვენ ალბათ არ კი შეამჩნევთ. 

კიდევ ერთი asymptotic სირთულის არის, ლოგარითმული დრო, O (შესვლა N). მაგალითი ალგორითმი, რომელიც ეშვება ამ სწრაფად არის კლასიკური ბინარული ძებნის ალგორითმი, მოძიების ელემენტს უკვე დახარისხებული სიის ელემენტების. 

თუ თქვენ არ იცით, რა ორობითი ძებნა აკეთებს, მე ამას თქვენთვის მართლაც სწრაფად. ვთქვათ თქვენ ვეძებთ ნომერი 3 ამ მასივი რიცხვებით. იგი უყურებს შუა ელემენტს მასივი და სთხოვს, "ეწოდება ელემენტის მინდა მეტია, ტოლი, ან ნაკლები ამ?" თუ ეს თანაბარი, მაშინ დიდი. თქვენ ი ელემენტს, და თქვენ კეთდება. თუ ეს უფრო დიდი, მაშინ თქვენ იცით ელემენტს უნდა იყოს მარჯვენა მხარეს მასივი, და თქვენ შეგიძლიათ მხოლოდ შევხედოთ, რომ მომავალში, და თუ პატარა, მაშინ თქვენ იცით, მას უნდა იყოს მარცხენა მხარეს. ეს პროცესი მაშინ განმეორდა პატარა ზომის მასივი სანამ სწორი ელემენტს არის ნაპოვნი. 

ეს მძლავრი ალგორითმის წყვეტს მასივი ზომა ნახევარ თითოეული ოპერაცია. ასე რომ, მოვძებნოთ ელემენტი დახარისხებული მასივი ზომა 8, უმეტეს (შესვლა ₂ 8), ან 3 ამ ოპერაციების, შემოწმების შუა ელემენტს, მაშინ ჭრის მასივი ნახევარ საჭირო იქნება, ხოლო მასივი ზომა 16 იღებს (შესვლა ₂ 16), ან 4 ოპერაციებში. სწორედ მხოლოდ 1 მეტი ოპერაცია გაორმაგდა ზომის მასივი. გაორმაგება ზომა მასივი ზრდის Runtime მხოლოდ 1 ბლოკი ეს კოდი. ერთხელ, შემოწმების შუა ელემენტს სიაში, მაშინ გაყოფის. ასე რომ, ის ამბობს მუშაობას ლოგარითმული დრო, O (შესვლა N). მაგრამ დაველოდოთ, თქვენ ამბობთ, არ ეს დამოკიდებულია სადაც სიაში ელემენტს თქვენ ეძებთ არის? რა მოხდება, თუ პირველ ელემენტს გადავხედავთ ხდება შეიძლება იყოს მარჯვენა ერთი? მაშინ, ეს მხოლოდ იღებს 1 ოპერაცია, რაც არ უნდა დიდი სია. 

ისე, რის გამოც კომპიუტერული მეცნიერები უფრო თვალსაზრისით ამისთვის asymptotic სირთულის რომელიც ასახავს ყველაზე კარგად საქმე და უარესი დადგმები ალგორითმი. სწორად, ზედა და ქვედა საზღვრები on runtime. საუკეთესო შემთხვევაში ბინარული ძებნა, ჩვენი ელემენტს არის უფლება არსებობს შუა, და ამას არ გაიგებთ მუდმივ დრო, რაც არ უნდა დიდი დანარჩენი მასივი. სიმბოლო გამოიყენება ეს Ω. ასე რომ, ეს ალგორითმი განაცხადა გასაშვებად წელს Ω (1). საუკეთესო შემთხვევაში, იგი აღმოაჩენს ელემენტს სწრაფად, რაც არ უნდა დიდი მასივი, მაგრამ უარეს შემთხვევაში, მას ასრულებს (შესვლა N) გაყოფილი ამოწმებს საქართველოს მასივი მოძიების უფლება ელემენტს. უარესი ზედა საზღვრები არის მოხსენიებული, ერთად დიდი "ო", რომ თქვენ უკვე იცით. ასე რომ, ეს O (შესვლა ო), მაგრამ Ω (1). 

ხაზოვანი ძებნა, პირიქით, რომელშიც თქვენ გავლა ყველა ელემენტს მასივი იპოვონ ერთი გსურთ, არის საუკეთესო Ω (1). ერთხელ, პირველი ელემენტს გსურთ. ასე რომ, არა აქვს მნიშვნელობა, რამდენად დიდი მასივი არის. ყველაზე ცუდ შემთხვევაში, ის ბოლო ელემენტია მასივი. ასე რომ, თქვენ უნდა გავლა ყველა N ელემენტების მასივი მის საპოვნელად, მინდა თუ ეძებდით 3. ასე რომ, იგი ეშვება O (N) ახლა რადგან პროპორციული რაოდენობის ელემენტების მასივი. 

კიდევ ერთი სიმბოლო გამოიყენება არის Θ. ეს შეიძლება გამოყენებულ იქნას აღწერს ალგორითმები სადაც საუკეთესო და ყველაზე უარესი შემთხვევები იგივეა. ეს არის საქმე string-სიგრძე ალგორითმები ჩვენ ვისაუბრეთ ადრე. ანუ, თუ ჩვენ ჩაწერს მას ცვლადი ადრე ჩვენ შესანახად სიმებიანი და ხელმისაწვდომობის მოგვიანებით მუდმივ დრო. არ აქვს მნიშვნელობა რა რაოდენობის ჩვენ შენახვის, რომ ცვლადი, ჩვენ უნდა შევხედოთ მას. საუკეთესო შემთხვევაში, ჩვენ შევხედოთ ეს და იპოვოს სიგრძეზე სიმებიანი. ამიტომ Ω (1) ან საუკეთესო შემთხვევაში, მუდმივი დრო. უარეს შემთხვევაში არის, შევხედავთ და იპოვოს სიგრძეზე სიმებიანი. ასე რომ, O (1) ან მუდმივი დროს უარეს შემთხვევაში. ასე რომ, რადგან საუკეთესო შემთხვევაში და უარეს შემთხვევაში იგივე, ეს შეიძლება ითქვას, რომ აწარმოებს Θ (1) დრო. 

წლის შემაჯამებელი, ჩვენ კარგი გზა მიზეზი შესახებ კოდები ეფექტურობის გარეშე იცის არაფერი რეალურ მსოფლიო დრო ისინი გასაშვებად, რომელიც გავლენას ახდენს უამრავი გარეთ ფაქტორები, მათ შორის განსხვავებული ტექნიკის, პროგრამული უზრუნველყოფის ან სპეციფიკას თქვენი კოდი. ასევე, საშუალებას გვაძლევს მიზეზი კარგად იმაზე, თუ რა მოხდება როდესაც ზომა საშუალებებით იზრდება. 

თუ თქვენ გაშვებული O (N) ² ალგორითმი, ან უარესი, O (2 ⁿ) ალგორითმი, ერთი ყველაზე სწრაფად მზარდი ტიპის, თქვენ მართლაც დაიწყოს შენიშნავს შენელება როდის გავუშვით მუშაობის უფრო დიდი რაოდენობით მონაცემები. 

სწორედ asymptotic სირთულის. მადლობა.