როგორც აღინიშნა დაკავშირებულ კითხვებზე პასუხში, ალგორითმის დროული სირთულის O(log n) ჩვეულებრივი გზაა, რომ ალგორითმმა იმუშაოს შეყვანის ზომის განმეორებით შემცირებით. გარკვეული მუდმივი ფაქტორით თითოეულ გამეორებაზე.
რას ნიშნავს log n?
O(log N) ძირითადად ნიშნავს დრო მიდის წრფივად, ხოლო n იზრდება ექსპონენციალურად. თუ 10 ელემენტის გამოთვლას 1 წამი დასჭირდება, 100 ელემენტის გამოთვლას 2 წამი დასჭირდება, 1000 ელემენტის გამოთვლას 3 წამი და ა.შ. ეს არის O(log n), როდესაც ჩვენ ვაკეთებთ ალგორითმების გაყოფას და დაპყრობას, მაგალითად, ორობითი ძებნა.
რა არის O და log n?
n ზომის შეყვანისთვის, O(n) ალგორითმი შეასრულებს ნაბიჯებს n-ის პროპორციულ ნაბიჯებს, ხოლო O(log(n)) სხვა ალგორითმი შეასრულებს ნაბიჯებს უხეშად log(n). აშკარად log(n) n-ზე მცირეა, ამიტომ სირთულის ალგორითმი O(log(n)) უკეთესია.
როგორ გამოვთვალოთ ჟურნალის n?
იდეა არის ის, რომ ალგორითმი არის O(log n), თუ სტრუქტურის 1-ზე 1-ზე გადახვევის ნაცვლად, თქვენ გაყოფთ სტრუქტურას შუაზე ისევ და ისევ და გააკეთებთ ოპერაციების მუდმივ რაოდენობას თითოეული გაყოფისთვის. საძიებო ალგორითმები, სადაც პასუხების სივრცე მუდმივად იყოფა, არის O(log n).
რა არის log n Square?
ჟურნალი ^2 (
) ნიშნავს, რომ ეს არის პროპორციული log -ის log ზომის პრობლემისთვის.
. ჟურნალი(
)^ 2 ნიშნავს, რომ ეს არისპროპორციულია კვადრატის -ის ლოგი.-ის პროპორციულია.
