|
Chiqish
Saralangan massiv: 11 12 22 25 34 64 90
Vaqt murakkabligi
|
| bet | 4/16 | | Sana | 15.11.2023 | | Hajmi | 29,81 Mb. | | #99092 |
Bog'liq Dilshoda Algoritm mustaqilChiqish
Saralangan massiv: 11 12 22 25 34 64 90
Vaqt murakkabligi: O(N 2 )
Yordamchi fazo: O(1)
Bubble Saralash uchun eng yomon holatlar tahlili:
Bubble Saralash uchun eng yomon holat massiv elementlari kamayish tartibida joylashtirilganida yuzaga keladi.
Eng yomon holatda, berilgan massivni saralash uchun zarur bo'lgan iteratsiya yoki o'tishlarning umumiy soni (n-1) ga teng. Bu erda "n" - massivda mavjud bo'lgan elementlar soni.
1-o'tishda: Taqqoslashlar soni = (n-1)
almashtirishlar soni = (n-1)
2-o'tishda: Taqqoslashlar soni = (n-2)
almashtirishlar soni = (n-2)
3-o'tishda: Taqqoslashlar soni = (n-3)
almashtirishlar soni = (n-3)
……….
n-1 o'tishda: Taqqoslashlar soni = 1
almashtirishlar soni = 1
Endi massivni tartiblash uchun zarur bo'lgan taqqoslashning umumiy sonini hisoblash
= (n-1) + (n-2) + (n-3) + . . . 2 + 1
= (n-1)*(n-1+1)/2 { N natural son formulasi yigʻindisi yordamida }
= n (n-1)/2
Eng yomon holatda:
Svoplarning umumiy soni = Taqqoslashning umumiy soni
Taqqoslashning umumiy soni (Eng yomon holat) = n(n-1)/2
Svoplarning umumiy soni (Eng yomon holat) = n(n-1)/2
Eng yomon va o'rtacha vaqt murakkabligi: O(N 2 ). Eng yomon holat massiv teskari tartiblanganda sodir bo'ladi.
Eng yaxshi ish vaqtining murakkabligi: O(N). Eng yaxshi holat massiv allaqachon tartiblangan bo'lsa sodir bo'ladi.
Yordamchi boʻshliq: O(1)
|
| |
