ΠΠ΅ΡΠΎΠ΄Ρ Π²Π½ΡΡΡΠ΅Π½Π½Π΅ΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ.
ΠΠ±ΠΌΠ΅Π½Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°.
Π‘ΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ Ρ Π΄ΡΡΠ³ΠΈΠΌΠΈ ΠΌΠ΅ΡΠΎΠ΄Π°ΠΌΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ
ΠΠ΅ΡΠΎΠ΄ ΠΏΡΠ·ΡΡΡΠΊΠ° Π΄ΠΎΠΏΡΡΠΊΠ°Π΅Ρ ΡΡΠΈ ΠΏΡΠΎΡΡΡΡ ΡΡΠΎΠ²Π΅ΡΡΠ΅Π½ΡΡΠ²ΠΎΠ²Π°Π½ΠΈΡ. ΠΠΎ-ΠΏΠ΅ΡΠ²ΡΡ , ΠΊΠ°ΠΊ ΠΏΠΎΠΊΠ°Π·ΡΠ²Π°Π΅Ρ ΡΠ°Π±Π»ΠΈΡΠ° 3, Π½Π° ΡΠ΅ΡΡΡΠ΅Ρ ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΡ ΡΠ°Π³Π°Ρ ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π½Π΅ ΠΌΠ΅Π½ΡΠ»ΠΎΡΡ, (ΠΌΠ°ΡΡΠΈΠ² ΠΎΠΊΠ°Π·Π°Π»ΡΡ ΡΠΆΠ΅ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΠΌ). ΠΠΎΡΡΠΎΠΌΡ, Π΅ΡΠ»ΠΈ Π½Π° Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠΌ ΡΠ°Π³Π΅ Π½Π΅ Π±ΡΠ»ΠΎ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΎ Π½ΠΈ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΎΠ±ΠΌΠ΅Π½Π°, ΡΠΎ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠ΅ΠΊΡΠ°ΡΠ°ΡΡ. ΠΠΎ-Π²ΡΠΎΡΡΡ , ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΏΠΎΠΌΠΈΠ½Π°ΡΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΈΠ½Π΄Π΅ΠΊΡΠ° ΠΌΠ°ΡΡΠΈΠ²Π°, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ΅ΡΠΎΠ΄Ρ Π²Π½ΡΡΡΠ΅Π½Π½Π΅ΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. ΠΠ±ΠΌΠ΅Π½Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°. Π‘ΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ Ρ Π΄ΡΡΠ³ΠΈΠΌΠΈ ΠΌΠ΅ΡΠΎΠ΄Π°ΠΌΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΠΠΠΠ‘Π’ΠΠ Π‘Π’ΠΠ ΠΠΠ ΠΠΠΠΠΠΠΠ― Π ΠΠ‘Π‘ΠΠΠ‘ΠΠΠ Π€ΠΠΠΠ ΠΠ¦ΠΠ ΠΠ£Π Π‘ΠΠΠΠ― Π ΠΠΠΠ’Π ΠΏΠΎ Π΄ΠΈΡΡΠΈΠΏΠ»ΠΈΠ½Π΅ «ΠΠ»Π³ΠΎΡΠΈΡΠΌΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠ΅Π½ΠΈΠ΅ ΠΠΠ‘».
Π½Π° ΡΠ΅ΠΌΡ «ΠΠ΅ΡΠΎΠ΄Ρ Π²Π½ΡΡΡΠ΅Π½Π½Π΅ΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. ΠΠ±ΠΌΠ΅Π½Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°.
Π‘ΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ Ρ Π΄ΡΡΠ³ΠΈΠΌΠΈ ΠΌΠ΅ΡΠΎΠ΄Π°ΠΌΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ".
2010 Π³.
1. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ΠΌ.
2. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π¨Π΅Π»Π»Π°.
3. ΠΠ±ΠΌΠ΅Π½Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°.
4. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ.
5. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ°Π·Π΄Π΅Π»Π΅Π½ΠΈΠ΅ΠΌ.
6. Π‘ΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΠΈΡΠ΅ΡΠ°ΡΡΡΠ°.
Π¦Π΅Π»ΡΡ Π΄Π°Π½Π½ΠΎΠΉ ΠΊΡΡΡΠΎΠ²ΠΎΠΉ ΡΠ°Π±ΠΎΡΡ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΈΠ·ΡΡΠ΅Π½ΠΈΡ ΠΎΡΠ½ΠΎΠ²Π½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Π²Π½ΡΡΡΠ΅Π½Π½Π΅ΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ² Π΄Π°Π½Π½ΡΡ , ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΈΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΈ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ. ΠΠΎΠ»Π΅Π΅ ΠΏΠΎΠ΄ΡΠΎΠ±Π½ΠΎ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅Π½ ΠΌΠ΅ΡΠΎΠ΄ ΠΎΠ±ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ.
ΠΡΠ»ΠΈ ΠΎΠ±ΡΠ°ΡΠΈΡΡΡΡ ΠΊ Π»ΠΈΡΠ΅ΡΠ°ΡΡΡΠ΅, ΡΠΎ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠ±Π½Π°ΡΡΠΆΠΈΡΡ Π΄Π²Π° ΠΊΡΠ°ΠΉΠ½ΠΈΡ ΠΏΠΎΠ΄Ρ ΠΎΠ΄Π° ΠΊ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡ ΠΌΠ°ΡΠ΅ΡΠΈΠ°Π»Π°. ΠΠ΅ΠΊΠΎΡΠΎΡΡΠ΅ Π°Π²ΡΠΎΡΡ Π»ΡΠ±ΡΡ ΠΈΠ·Π»Π°Π³Π°ΡΡ ΠΌΠ°ΡΠ΅ΡΠΈΠ°Π» Π½Π° Π²ΡΡΠΎΠΊΠΎΠΌ ΡΠ΅ΠΎΡΠ΅ΡΠΈΡΠ΅ΡΠΊΠΎΠΌ ΡΡΠΎΠ²Π½Π΅. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, Π΄Π»Ρ ΡΠΎΠ³ΠΎ, ΡΡΠΎΠ±Ρ Π²Π²Π΅ΡΡΠΈ ΠΏΠΎΠ½ΡΡΠΈΠ΅ ΡΠΈΠΏΠ° Π΄Π°Π½Π½ΡΡ ΠΈ ΠΏΡΠ΅Π΄Π»ΠΎΠΆΠΈΡΡ ΠΊΠ»Π°ΡΡΠΈΡΠΈΠΊΠ°ΡΠΈΡ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΡΡ ΡΠΈΠΏΠΎΠ², ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΡΡ ΡΠ°Π·Π²ΠΈΡΡΠ΅ ΠΌΠ΅Ρ Π°Π½ΠΈΠ·ΠΌΡ Π°Π±ΡΡΡΠ°ΠΊΡΠ½ΠΎΠΉ Π°Π»Π³Π΅Π±ΡΡ; ΠΏΡΠΈ ΠΎΠΏΠΈΡΠ°Π½ΠΈΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Π² ΠΎΠ±ΡΠ·Π°ΡΠ΅Π»ΡΠ½ΠΎΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅ ΠΏΡΠΈΠ²ΠΎΠ΄ΡΡΡΡ Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΎΡΠ΅Π½ΠΊΠΈ ΠΈΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ. ΠΡΡΠ³ΠΎΠΉ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ ΡΠΎΡΡΠΎΠΈΡ Π² ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌ ΠΏΡΠΈΠ±Π»ΠΈΠΆΠ΅Π½ΠΈΠΈ ΠΊ ΠΏΡΠ°ΠΊΡΠΈΠΊΠ΅. ΠΠ±ΡΡΠ½ΠΎ Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΡΠΉ ΡΠ·ΡΠΊ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ, ΠΈ Π²ΡΠ΅ ΠΎΠΏΠΈΡΡΠ²Π°Π΅ΠΌΡΠ΅ ΡΡΡΡΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ ΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΡΡΡ Π½Π° ΡΡΠΎΠΌ ΡΠ·ΡΠΊΠ΅.
1. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ΠΌ.
ΠΠ΄Π½ΠΈΠΌ ΠΈΠ· Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΠΏΡΠΎΡΡΡΡ ΠΈ Π΅ΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² Π²Π½ΡΡΡΠ΅Π½Π½Π΅ΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Ρ ΠΏΡΠΎΡΡΡΠΌΠΈ Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΡΠΌΠΈ. ΠΠ΄Π΅Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΎΡΠ΅Π½Ρ ΠΏΡΠΎΡΡΠ°. ΠΡΡΡΡ ΠΈΠΌΠ΅Π΅ΡΡΡ ΠΌΠ°ΡΡΠΈΠ² ΠΊΠ»ΡΡΠ΅ΠΉ a[1], a[2], …, a[n]. ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° ΠΌΠ°ΡΡΠΈΠ²Π°, Π½Π°ΡΠΈΠ½Π°Ρ ΡΠΎ Π²ΡΠΎΡΠΎΠ³ΠΎ, ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡΡ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ Ρ ΠΌΠ΅Π½ΡΡΠΈΠΌ ΠΈΠ½Π΄Π΅ΠΊΡΠΎΠΌ (ΡΠ»Π΅ΠΌΠ΅Π½Ρ a[i] ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ ΡΡΠ°Π²Π½ΠΈΠ²Π°Π΅ΡΡΡ Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ a[i-1], a[i-2] …) ΠΈ Π΄ΠΎ ΡΠ΅Ρ ΠΏΠΎΡ, ΠΏΠΎΠΊΠ° Π΄Π»Ρ ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° a[j] Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΡΠΎΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΠ΅ a[j] > a[i], a[i] ΠΈ a[j] ΠΌΠ΅Π½ΡΡΡΡΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ. ΠΡΠ»ΠΈ ΡΠ΄Π°Π΅ΡΡΡ Π²ΡΡΡΠ΅ΡΠΈΡΡ ΡΠ°ΠΊΠΎΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ a[j], ΡΡΠΎ a[j] <= a[i], ΠΈΠ»ΠΈ Π΅ΡΠ»ΠΈ Π΄ΠΎΡΡΠΈΠ³Π½ΡΡΠ° Π½ΠΈΠΆΠ½ΡΡ Π³ΡΠ°Π½ΠΈΡΠ° ΠΌΠ°ΡΡΠΈΠ²Π°, ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡΡ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄ ΠΊ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° a[i+1] (ΠΏΠΎΠΊΠ° Π½Π΅ Π±ΡΠ΄Π΅Ρ Π΄ΠΎΡΡΠΈΠ³Π½ΡΡΠ° Π²Π΅ΡΡ Π½ΡΡ Π³ΡΠ°Π½ΠΈΡΠ° ΠΌΠ°ΡΡΠΈΠ²Π°).
ΠΠ΅Π³ΠΊΠΎ Π²ΠΈΠ΄Π΅ΡΡ, ΡΡΠΎ Π² Π»ΡΡΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ (ΠΊΠΎΠ³Π΄Π° ΠΌΠ°ΡΡΠΈΠ² ΡΠΆΠ΅ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½) Π΄Π»Ρ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Ρ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠΌ ΠΈΠ· n ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΏΠΎΡΡΠ΅Π±ΡΠ΅ΡΡΡ n-1 ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ ΠΈ 0 ΠΏΠ΅ΡΠ΅ΡΡΠ»ΠΎΠΊ. Π Ρ ΡΠ΄ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ (ΠΊΠΎΠ³Π΄Π° ΠΌΠ°ΡΡΠΈΠ² ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½ Π² ΠΎΠ±ΡΠ°ΡΠ½ΠΎΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅) ΠΏΠΎΡΡΠ΅Π±ΡΠ΅ΡΡΡ n?(n-1)/2 ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ ΠΈ ΡΡΠΎΠ»ΡΠΊΠΎ ΠΆΠ΅ ΠΏΠ΅ΡΠ΅ΡΡΠ»ΠΎΠΊ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΌΠΎΠΆΠ½ΠΎ ΠΎΡΠ΅Π½ΠΈΠ²Π°ΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΠΌΠ΅ΡΠΎΠ΄Π° ΠΏΡΠΎΡΡΡΡ Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΠΉ ΠΊΠ°ΠΊ O (n2).
ΠΠΎΠΆΠ½ΠΎ ΡΠΎΠΊΡΠ°ΡΠΈΡΡ ΡΠΈΡΠ»ΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ, ΠΏΡΠΈΠΌΠ΅Π½ΡΠ΅ΠΌΡΡ Π² ΠΌΠ΅ΡΠΎΠ΄Π΅ ΠΏΡΠΎΡΡΡΡ Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΠΉ, Π΅ΡΠ»ΠΈ Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ ΡΠ΅ΠΌ ΡΠ°ΠΊΡΠΎΠΌ, ΡΡΠΎ ΠΏΡΠΈ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° a[i] ΠΌΠ°ΡΡΠΈΠ²Π° ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ a[1], a[2], …, a[i-1] ΡΠΆΠ΅ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Ρ, ΠΈ Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ Π΄Π»Ρ ΠΏΠΎΠΈΡΠΊΠ° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, Ρ ΠΊΠΎΡΠΎΡΡΠΌ Π΄ΠΎΠ»ΠΆΠ½Π° Π±ΡΡΡ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½Π° ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠ°, ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π΄Π²ΠΎΠΈΡΠ½ΠΎΠ³ΠΎ Π΄Π΅Π»Π΅Π½ΠΈΡ. Π ΡΡΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΎΡΠ΅Π½ΠΊΠ° ΡΠΈΡΠ»Π° ΡΡΠ΅Π±ΡΠ΅ΠΌΡΡ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ ΡΡΠ°Π½ΠΎΠ²ΠΈΡΡΡ O (n?log n). ΠΠ°ΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΏΡΠΈ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠΈ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΡΡΠ΅Π±ΡΠ΅ΡΡΡ ΡΠ΄Π²ΠΈΠΆΠΊΠ° Π½Π° ΠΎΠ΄ΠΈΠ½ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΡΠΎ ΠΎΡΠ΅Π½ΠΊΠ° ΡΠΈΡΠ»Π° ΠΏΠ΅ΡΠ΅ΡΡΠ»ΠΎΠΊ ΠΎΡΡΠ°Π΅ΡΡΡ O (n2).
Π’Π°Π±Π»ΠΈΡΠ° 1.1 ΠΡΠΈΠΌΠ΅Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΏΡΠΎΡΡΠΎΠ³ΠΎ Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΡ.
ΠΠ°ΡΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π°. | 8 23 5 65 44 33 1 6. | |
Π¨Π°Π³ 1. | 8 23 5 65 44 33 1 6. | |
Π¨Π°Π³ 2. | 8 5 23 65 44 33 1 6. 5 8 23 65 44 33 1 6. | |
Π¨Π°Π³ 3. | 5 8 23 65 44 33 1 6. | |
Π¨Π°Π³ 4. | 5 8 23 44 65 33 1 6. | |
Π¨Π°Π³ 5. | 5 8 23 44 33 65 1 6. 5 8 23 33 44 65 1 6. | |
Π¨Π°Π³ 6. | 5 8 23 33 44 1 65 6. 5 8 23 33 1 44 65 6. 5 8 23 1 33 44 65 6. 5 8 1 23 33 44 65 6. 5 1 8 23 33 44 65 6. 1 5 8 23 33 44 65 6. | |
Π¨Π°Π³ 7. | 1 5 8 23 33 44 6 65. 1 5 8 23 33 6 44 65. 1 5 8 23 6 33 44 65. 1 5 8 6 23 33 44 65. 1 5 6 8 23 33 44 65. | |
2. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π¨Π΅Π»Π»Π°.
ΠΠ°Π»ΡΠ½Π΅ΠΉΡΠΈΠΌ ΡΠ°Π·Π²ΠΈΡΠΈΠ΅ΠΌ ΠΌΠ΅ΡΠΎΠ΄Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Ρ Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΡΠΌΠΈ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π¨Π΅Π»Π»Π°, Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠ°Ρ ΠΏΠΎ-Π΄ΡΡΠ³ΠΎΠΌΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΎΠΉ Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΡΠΌΠΈ Ρ ΡΠΌΠ΅Π½ΡΡΠ°ΡΡΠΈΠΌΡΡ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ΠΌ. ΠΡ Π½Π΅ Π±ΡΠ΄Π΅ΠΌ ΠΎΠΏΠΈΡΡΠ²Π°ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π² ΠΎΠ±ΡΠ΅ΠΌ Π²ΠΈΠ΄Π΅, Π° ΠΎΠ³ΡΠ°Π½ΠΈΡΠΈΠΌΡΡ ΡΠ»ΡΡΠ°Π΅ΠΌ, ΠΊΠΎΠ³Π΄Π° ΡΠΈΡΠ»ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π² ΡΠΎΡΡΠΈΡΡΠ΅ΠΌΠΎΠΌ ΠΌΠ°ΡΡΠΈΠ²Π΅ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ ΡΠΈΡΠ»Π° 2. ΠΠ»Ρ ΠΌΠ°ΡΡΠΈΠ²Π° Ρ 2n ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ. ΠΠ° ΠΏΠ΅ΡΠ²ΠΎΠΉ ΡΠ°Π·Π΅ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ΠΌ Π²ΡΠ΅Ρ ΠΏΠ°Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΌΠ°ΡΡΠΈΠ²Π°, ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΠΊΠΎΡΠΎΡΡΠΌΠΈ Π΅ΡΡΡ 2(n-1). ΠΠ° Π²ΡΠΎΡΠΎΠΉ ΡΠ°Π·Π΅ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π°, ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΠΊΠΎΡΠΎΡΡΠΌΠΈ Π΅ΡΡΡ 2(n-2). Π ΡΠ°ΠΊ Π΄Π°Π»Π΅Π΅, ΠΏΠΎΠΊΠ° ΠΌΡ Π½Π΅ Π΄ΠΎΠΉΠ΄Π΅ΠΌ Π΄ΠΎ ΡΠ°Π·Ρ Ρ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ΠΌ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ, ΡΠ°Π²Π½ΡΠΌ Π΅Π΄ΠΈΠ½ΠΈΡΠ΅, ΠΈ Π½Π΅ Π²ΡΠΏΠΎΠ»Π½ΠΈΠΌ Π·Π°Π²Π΅ΡΡΠ°ΡΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ Ρ Π²ΠΊΠ»ΡΡΠ΅Π½ΠΈΡΠΌΠΈ. ΠΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΠΌΠ΅ΡΠΎΠ΄Π° Π¨Π΅Π»Π»Π° ΠΊ ΠΌΠ°ΡΡΠΈΠ²Ρ, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΠΎΠΌΡ Π² Π½Π°ΡΠΈΡ ΠΏΡΠΈΠΌΠ΅ΡΠ°Ρ , ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ Π² ΡΠ°Π±Π»ΠΈΡΠ΅ 2.2.
Π’Π°Π±Π»ΠΈΡΠ°1.2. ΠΡΠΈΠΌΠ΅Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π¨Π΅Π»Π».
ΠΠ°ΡΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π°. | 8 23 5 65 44 33 1 6. | |
Π€Π°Π·Π° 1 (ΡΠΎΡΡΠΈΡΡΡΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΠΊΠΎΡΠΎΡΡΠΌΠΈ ΡΠ΅ΡΡΡΠ΅). | 8 23 5 65 44 33 1 6. 8 23 5 65 44 33 1 6. 8 23 1 65 44 33 5 6. 8 23 1 6 44 33 5 65. | |
Π€Π°Π·Π° 2 (ΡΠΎΡΡΠΈΡΡΡΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΠΊΠΎΡΠΎΡΡΠΌΠΈ Π΄Π²Π°). | 1 23 8 6 44 33 5 65. 1 23 8 6 44 33 5 65. 1 23 8 6 5 33 44 65. 1 23 5 6 8 33 44 65. 1 6 5 23 8 33 44 65. 1 6 5 23 8 33 44 65. 1 6 5 23 8 33 44 65. | |
Π€Π°Π·Π° 3 (ΡΠΎΡΡΠΈΡΡΡΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΠΊΠΎΡΠΎΡΡΠΌΠΈ ΠΎΠ΄ΠΈΠ½). | 1 6 5 23 8 33 44 65. 1 5 6 23 8 33 44 65. 1 5 6 23 8 33 44 65. 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. | |
Π ΠΎΠ±ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌ Π¨Π΅Π»Π»Π° Π΅ΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎ ΠΏΠ΅ΡΠ΅ΡΠΎΡΠΌΡΠ»ΠΈΡΡΠ΅ΡΡΡ Π΄Π»Ρ Π·Π°Π΄Π°Π½Π½ΠΎΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ ΠΈΠ· t ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠΉ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ h1, h2, …, ht, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΡΡ Π²ΡΠΏΠΎΠ»Π½ΡΡΡΡΡ ΡΡΠ»ΠΎΠ²ΠΈΡ h1 = 1 ΠΈ h (i+1) < hi. ΠΠΎΠ½Π°Π»ΡΠ΄ ΠΠ½ΡΡ ΠΏΠΎΠΊΠ°Π·Π°Π», ΡΡΠΎ ΠΏΡΠΈ ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎ ΠΏΠΎΠ΄ΠΎΠ±ΡΠ°Π½Π½ΡΡ t ΠΈ h ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π¨Π΅Π»Π»Π° ΡΠ²Π»ΡΠ΅ΡΡΡ O (n (1.2)), ΡΡΠΎ ΡΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎ ΠΌΠ΅Π½ΡΡΠ΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΏΡΠΎΡΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ.
3. ΠΠ±ΠΌΠ΅Π½Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°.
ΠΡΠΎΡΡΠ°Ρ ΠΎΠ±ΠΌΠ΅Π½Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° (Π² ΠΏΡΠΎΡΡΠΎΡΠ΅ΡΠΈΠΈ Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠ°Ρ «ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΏΡΠ·ΡΡΡΠΊΠ°») Π΄Π»Ρ ΠΌΠ°ΡΡΠΈΠ²Π° a[1], a[2], …, a[n] ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ. ΠΠ°ΡΠΈΠ½Π°Ρ Ρ ΠΊΠΎΠ½ΡΠ° ΠΌΠ°ΡΡΠΈΠ²Π° ΡΡΠ°Π²Π½ΠΈΠ²Π°ΡΡΡΡ Π΄Π²Π° ΡΠΎΡΠ΅Π΄Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° (a[n] ΠΈ a[n-1]). ΠΡΠ»ΠΈ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΡΡΠ»ΠΎΠ²ΠΈΠ΅ a[n-1] > a[n], ΡΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΌΠ΅Π½ΡΡΡΡΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ. ΠΡΠΎΡΠ΅ΡΡ ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠ°Π΅ΡΡΡ Π΄Π»Ρ a[n-1] ΠΈ a[n-2] ΠΈ Ρ. Π΄., ΠΏΠΎΠΊΠ° Π½Π΅ Π±ΡΠ΄Π΅Ρ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ a[2] ΠΈ a[1]. ΠΠΎΠ½ΡΡΠ½ΠΎ, ΡΡΠΎ ΠΏΠΎΡΠ»Π΅ ΡΡΠΎΠ³ΠΎ Π½Π° ΠΌΠ΅ΡΡΠ΅ a[1] ΠΎΠΊΠ°ΠΆΠ΅ΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΠ²Π° Ρ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΠΌ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ. ΠΠ° Π²ΡΠΎΡΠΎΠΌ ΡΠ°Π³Π΅ ΠΏΡΠΎΡΠ΅ΡΡ ΠΏΠΎΠ²ΡΠΎΡΡΠ΅ΡΡΡ, Π½ΠΎ ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΠΌΠΈ ΡΡΠ°Π²Π½ΠΈΠ²Π°ΡΡΡΡ a[3] ΠΈ a[2]. Π ΡΠ°ΠΊ Π΄Π°Π»Π΅Π΅. ΠΠ° ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅ΠΌ ΡΠ°Π³Π΅ Π±ΡΠ΄ΡΡ ΡΡΠ°Π²Π½ΠΈΠ²Π°ΡΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΡΠ΅ΠΊΡΡΠΈΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΡ a[n] ΠΈ a[n-1]. ΠΠΎΠ½ΡΡΠ½Π° Π°Π½Π°Π»ΠΎΠ³ΠΈΡ Ρ ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ, ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ (ΡΠ°ΠΌΡΠ΅ «Π»Π΅Π³ΠΊΠΈΠ΅») ΠΏΠΎΡΡΠ΅ΠΏΠ΅Π½Π½ΠΎ «Π²ΡΠΏΠ»ΡΠ²Π°ΡΡ» ΠΊ Π²Π΅ΡΡ Π½Π΅ΠΉ Π³ΡΠ°Π½ΠΈΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π°. ΠΡΠΈΠΌΠ΅Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΏΡΠ·ΡΡΡΠΊΠ° ΠΏΠΎΠΊΠ°Π·Π°Π½ Π² ΡΠ°Π±Π»ΠΈΡΠ΅ 2.3.
Π’Π°Π±Π»ΠΈΡΠ° 1.3. ΠΡΠΈΠΌΠ΅Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΡΠ·ΡΡΡΠΊΠ°.
ΠΠ°ΡΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π°. | 8 23 5 65 44 33 1 6. | |
Π¨Π°Π³ 1. | 8 23 5 65 44 33 1 6. 8 23 5 65 44 1 33 6. 8 23 5 65 1 44 33 6. 8 23 5 1 65 44 33 6. 8 23 1 5 65 44 33 6. 8 1 23 5 65 44 33 6. 1 8 23 5 65 44 33 6. | |
Π¨Π°Π³ 2. | 1 8 23 5 65 44 6 33. 1 8 23 5 65 6 44 33. 1 8 23 5 6 65 44 33. 1 8 23 5 6 65 44 33. 1 8 5 23 6 65 44 33. 1 5 8 23 6 65 44 33. | |
Π¨Π°Π³ 3. | 1 5 8 23 6 65 33 44. 1 5 8 23 6 33 65 44. 1 5 8 23 6 33 65 44. 1 5 8 6 23 33 65 44. 1 5 6 8 23 33 65 44. | |
Π¨Π°Π³ 4. | 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. | |
Π¨Π°Π³ 5. | 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. | |
Π¨Π°Π³ 6. | 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. | |
Π¨Π°Π³ 7. | 1 5 6 8 23 33 44 65. | |
ΠΠ»Ρ ΠΌΠ΅ΡΠΎΠ΄Π° ΠΏΡΠΎΡΡΠΎΠΉ ΠΎΠ±ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΡΠ΅Π±ΡΠ΅ΡΡΡ ΡΠΈΡΠ»ΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ nx(n-1)/2, ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ ΠΏΠ΅ΡΠ΅ΡΡΠ»ΠΎΠΊ 0, Π° ΡΡΠ΅Π΄Π½Π΅Π΅ ΠΈ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ ΠΏΠ΅ΡΠ΅ΡΡΠ»ΠΎΠΊ — O (n2).
ΠΠ΅ΡΠΎΠ΄ ΠΏΡΠ·ΡΡΡΠΊΠ° Π΄ΠΎΠΏΡΡΠΊΠ°Π΅Ρ ΡΡΠΈ ΠΏΡΠΎΡΡΡΡ ΡΡΠΎΠ²Π΅ΡΡΠ΅Π½ΡΡΠ²ΠΎΠ²Π°Π½ΠΈΡ. ΠΠΎ-ΠΏΠ΅ΡΠ²ΡΡ , ΠΊΠ°ΠΊ ΠΏΠΎΠΊΠ°Π·ΡΠ²Π°Π΅Ρ ΡΠ°Π±Π»ΠΈΡΠ° 3, Π½Π° ΡΠ΅ΡΡΡΠ΅Ρ ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΡ ΡΠ°Π³Π°Ρ ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π½Π΅ ΠΌΠ΅Π½ΡΠ»ΠΎΡΡ, (ΠΌΠ°ΡΡΠΈΠ² ΠΎΠΊΠ°Π·Π°Π»ΡΡ ΡΠΆΠ΅ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΠΌ). ΠΠΎΡΡΠΎΠΌΡ, Π΅ΡΠ»ΠΈ Π½Π° Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠΌ ΡΠ°Π³Π΅ Π½Π΅ Π±ΡΠ»ΠΎ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΎ Π½ΠΈ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΎΠ±ΠΌΠ΅Π½Π°, ΡΠΎ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠ΅ΠΊΡΠ°ΡΠ°ΡΡ. ΠΠΎ-Π²ΡΠΎΡΡΡ , ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΏΠΎΠΌΠΈΠ½Π°ΡΡ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΈΠ½Π΄Π΅ΠΊΡΠ° ΠΌΠ°ΡΡΠΈΠ²Π°, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π½Π° ΡΠ΅ΠΊΡΡΠ΅ΠΌ ΡΠ°Π³Π΅ Π²ΡΠΏΠΎΠ»Π½ΡΠ»ΠΈΡΡ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ. ΠΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, ΡΡΠΎ Π²Π΅ΡΡ Π½ΡΡ ΡΠ°ΡΡΡ ΠΌΠ°ΡΡΠΈΠ²Π° Π΄ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Ρ ΡΡΠΈΠΌ ΠΈΠ½Π΄Π΅ΠΊΡΠΎΠΌ ΡΠΆΠ΅ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π°, ΠΈ Π½Π° ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ ΡΠ°Π³Π΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠ΅ΠΊΡΠ°ΡΠ°ΡΡ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ ΡΠΎΡΠ΅Π΄Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΏΡΠΈ Π΄ΠΎΡΡΠΈΠΆΠ΅Π½ΠΈΠΈ ΡΠ°ΠΊΠΎΠ³ΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΈΠ½Π΄Π΅ΠΊΡΠ°. Π-ΡΡΠ΅ΡΡΠΈΡ , ΠΌΠ΅ΡΠΎΠ΄ ΠΏΡΠ·ΡΡΡΠΊΠ° ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π½Π΅ΡΠ°Π²Π½ΠΎΠΏΡΠ°Π²Π½ΠΎ Π΄Π»Ρ «Π»Π΅Π³ΠΊΠΈΡ » ΠΈ «ΡΡΠΆΠ΅Π»ΡΡ » Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ. ΠΠ΅Π³ΠΊΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΏΠΎΠΏΠ°Π΄Π°Π΅Ρ Π½Π° Π½ΡΠΆΠ½ΠΎΠ΅ ΠΌΠ΅ΡΡΠΎ Π·Π° ΠΎΠ΄ΠΈΠ½ ΡΠ°Π³, Π° ΡΡΠΆΠ΅Π»ΠΎΠ΅ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΠΎΠΏΡΡΠΊΠ°Π΅ΡΡΡ ΠΏΠΎ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ ΠΊ Π½ΡΠΆΠ½ΠΎΠΌΡ ΠΌΠ΅ΡΡΡ Π½Π° ΠΎΠ΄Π½Ρ ΠΏΠΎΠ·ΠΈΡΠΈΡ.
ΠΠ° ΡΡΠΈΡ Π½Π°Π±Π»ΡΠ΄Π΅Π½ΠΈΡΡ ΠΎΡΠ½ΠΎΠ²Π°Π½ ΠΌΠ΅ΡΠΎΠ΄ ΡΠ΅ΠΉΠΊΠ΅ΡΠ½ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ (ShakerSort). ΠΡΠΈ Π΅Π³ΠΎ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠΈ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ ΡΠ°Π³Π΅ ΠΌΠ΅Π½ΡΠ΅ΡΡΡ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΡΠΌΠΎΡΡΠ°. Π ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ Π½Π° ΠΎΠ΄Π½ΠΎΠΌ ΡΠ°Π³Π΅ «Π²ΡΠΏΠ»ΡΠ²Π°Π΅Ρ» ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠΉ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Π»Π΅Π³ΠΊΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ, Π° Π½Π° Π΄ΡΡΠ³ΠΎΠΌ «ΡΠΎΠ½Π΅Ρ» ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠΉ ΡΠ°ΠΌΡΠΉ ΡΡΠΆΠ΅Π»ΡΠΉ. ΠΡΠΈΠΌΠ΅Ρ ΡΠ΅ΠΉΠΊΠ΅ΡΠ½ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½ Π² ΡΠ°Π±Π»ΠΈΡΠ΅ 2.4.
Π’Π°Π±Π»ΠΈΡΠ° 4. ΠΡΠΈΠΌΠ΅Ρ ΡΠ΅ΠΉΠΊΠ΅ΡΠ½ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ.
ΠΠ°ΡΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π°. | 8 23 5 65 44 33 1 6. | |
Π¨Π°Π³ 1. | 8 23 5 65 44 33 1 6. 8 23 5 65 44 1 33 6. 8 23 5 65 1 44 33 6. 8 23 5 1 65 44 33 6. 8 23 1 5 65 44 33 6. 8 1 23 5 65 44 33 6. 1 8 23 5 65 44 33 6. | |
Π¨Π°Π³ 2. | 1 8 23 5 65 44 33 6. 1 8 5 23 65 44 33 6. 1 8 5 23 65 44 33 6. 1 8 5 23 44 65 33 6. 1 8 5 23 44 33 65 6. 1 8 5 23 44 33 6 65. | |
Π¨Π°Π³ 3. | 1 8 5 23 44 6 33 65. 1 8 5 23 6 44 33 65. 1 8 5 6 23 44 33 65. 1 8 5 6 23 44 33 65. 1 5 8 6 23 44 33 65. | |
Π¨Π°Π³ 4. | 1 5 6 8 23 44 33 65. 1 5 6 8 23 44 33 65. 1 5 6 8 23 44 33 65. 1 5 6 8 23 33 44 65. | |
Π¨Π°Π³ 5. | 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. 1 5 6 8 23 33 44 65. | |
Π¨Π΅ΠΉΠΊΠ΅ΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΡΠΎΠΊΡΠ°ΡΠΈΡΡ ΡΠΈΡΠ»ΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ (ΠΏΠΎ ΠΎΡΠ΅Π½ΠΊΠ΅ ΠΠ½ΡΡΠ° ΡΡΠ΅Π΄Π½ΠΈΠΌ ΡΠΈΡΠ»ΠΎΠΌ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ ΡΠ²Π»ΡΠ΅ΡΡΡ (n2 — n?(const + ln n)), Ρ ΠΎΡΡ ΠΏΠΎΡΡΠ΄ΠΊΠΎΠΌ ΠΎΡΠ΅Π½ΠΊΠΈ ΠΏΠΎ-ΠΏΡΠ΅ΠΆΠ½Π΅ΠΌΡ ΠΎΡΡΠ°Π΅ΡΡΡ n2. Π§ΠΈΡΠ»ΠΎ ΠΆΠ΅ ΠΏΠ΅ΡΠ΅ΡΡΠ»ΠΎΠΊ, Π²ΠΎΠΎΠ±ΡΠ΅ Π³ΠΎΠ²ΠΎΡΡ, Π½Π΅ ΠΌΠ΅Π½ΡΠ΅ΡΡΡ. Π¨Π΅ΠΉΠΊΠ΅ΡΠ½ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ ΡΠ΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡΠ΅ΡΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π² ΡΠ΅Ρ ΡΠ»ΡΡΠ°ΡΡ , ΠΊΠΎΠ³Π΄Π° ΠΈΠ·Π²Π΅ΡΡΠ½ΠΎ, ΡΡΠΎ ΠΌΠ°ΡΡΠΈΠ² «ΠΏΠΎΡΡΠΈ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½» .
4. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ.
ΠΡΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π° a[1], a[2], …, a[n] ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΏΡΠΎΡΡΠΎΠ³ΠΎ Π²ΡΠ±ΠΎΡΠ° ΡΡΠ΅Π΄ΠΈ Π²ΡΠ΅Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Ρ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠΈΠΌ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ a[i], ΠΈ a[1] ΠΈ a[i] ΠΎΠ±ΠΌΠ΅Π½ΠΈΠ²Π°ΡΡΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌΠΈ. ΠΠ°ΡΠ΅ΠΌ ΡΡΠΎΡ ΠΏΡΠΎΡΠ΅ΡΡ ΠΏΠΎΠ²ΡΠΎΡΡΠ΅ΡΡΡ Π΄Π»Ρ ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌΡΡ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ² a[2], a[3], …, a[n], … a[j], a[j+1], …, a[n] Π΄ΠΎ ΡΠ΅Ρ ΠΏΠΎΡ, ΠΏΠΎΠΊΠ° ΠΌΡ Π½Π΅ Π΄ΠΎΠΉΠ΄Π΅ΠΌ Π΄ΠΎ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Π° a[n], ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠ΅Π³ΠΎ ΠΊ ΡΡΠΎΠΌΡ ΠΌΠΎΠΌΠ΅Π½ΡΡ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅Π΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅. Π Π°Π±ΠΎΡΠ° Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΈΠ»Π»ΡΡΡΡΠΈΡΡΠ΅ΡΡΡ ΠΏΡΠΈΠΌΠ΅ΡΠΎΠΌ Π² ΡΠ°Π±Π»ΠΈΡΠ΅ 2.5.
Π’Π°Π±Π»ΠΈΡΠ° 5. ΠΡΠΈΠΌΠ΅Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠΎΡΡΡΠΌ Π²ΡΠ±ΠΎΡΠΎΠΌ.
ΠΠ°ΡΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π°. | 8 23 5 65 44 33 1 6. | |
Π¨Π°Π³ 1. | 1 23 5 65 44 33 8 6. | |
Π¨Π°Π³ 2. | 1 5 23 65 44 33 8 6. | |
Π¨Π°Π³ 3. | 1 5 6 65 44 33 8 23. | |
Π¨Π°Π³ 4. | 1 5 6 8 44 33 65 23. | |
Π¨Π°Π³ 5. | 1 5 6 8 33 44 65 23. | |
Π¨Π°Π³ 6. | 1 5 6 8 23 44 65 33. | |
Π¨Π°Π³ 7. | 1 5 6 8 23 33 65 44. | |
Π¨Π°Π³ 8. | 1 5 6 8 23 33 44 65. | |
ΠΠ»Ρ ΠΌΠ΅ΡΠΎΠ΄Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠΎΡΡΡΠΌ Π²ΡΠ±ΠΎΡΠΎΠΌ ΡΡΠ΅Π±ΡΠ΅ΠΌΠΎΠ΅ ΡΠΈΡΠ»ΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ — nx(n-1)/2. ΠΠΎΡΡΠ΄ΠΎΠΊ ΡΡΠ΅Π±ΡΠ΅ΠΌΠΎΠ³ΠΎ ΡΠΈΡΠ»Π° ΠΏΠ΅ΡΠ΅ΡΡΠ»ΠΎΠΊ (Π²ΠΊΠ»ΡΡΠ°Ρ ΡΠ΅, ΠΊΠΎΡΠΎΡΡΠ΅ ΡΡΠ΅Π±ΡΡΡΡΡ Π΄Π»Ρ Π²ΡΠ±ΠΎΡΠ° ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°) Π² Ρ ΡΠ΄ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΠΎΡΡΠ°Π²Π»ΡΠ΅Ρ O (n2). ΠΠ΄Π½Π°ΠΊΠΎ ΠΏΠΎΡΡΠ΄ΠΎΠΊ ΡΡΠ΅Π΄Π½Π΅Π³ΠΎ ΡΠΈΡΠ»Π° ΠΏΠ΅ΡΠ΅ΡΡΠ»ΠΎΠΊ Π΅ΡΡΡ O (n?ln n), ΡΡΠΎ Π² ΡΡΠ΄Π΅ ΡΠ»ΡΡΠ°Π΅Π² Π΄Π΅Π»Π°Π΅Ρ ΡΡΠΎΡ ΠΌΠ΅ΡΠΎΠ΄ ΠΏΡΠ΅Π΄ΠΏΠΎΡΡΠΈΡΠ΅Π»ΡΠ½ΡΠΌ.
5. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ°Π·Π΄Π΅Π»Π΅Π½ΠΈΠ΅ΠΌ (Quicksort).
ΠΠ΅ΡΠΎΠ΄ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ°Π·Π΄Π΅Π»Π΅Π½ΠΈΠ΅ΠΌ Π±ΡΠ» ΠΏΡΠ΅Π΄Π»ΠΎΠΆΠ΅Π½ Π§Π°ΡΠ»ΡΠ·ΠΎΠΌ Π₯ΠΎΠ°ΡΠΎΠΌ (ΠΎΠ½ Π»ΡΠ±ΠΈΡ Π½Π°Π·ΡΠ²Π°ΡΡ ΡΠ΅Π±Ρ Π’ΠΎΠ½ΠΈ) Π² 1962 Π³. ΠΡΠΎΡ ΠΌΠ΅ΡΠΎΠ΄ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ°Π·Π²ΠΈΡΠΈΠ΅ΠΌ ΠΌΠ΅ΡΠΎΠ΄Π° ΠΏΡΠΎΡΡΠΎΠ³ΠΎ ΠΎΠ±ΠΌΠ΅Π½Π° ΠΈ Π½Π°ΡΡΠΎΠ»ΡΠΊΠΎ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π΅Π½, ΡΡΠΎ Π΅Π³ΠΎ ΡΡΠ°Π»ΠΈ Π½Π°Π·ΡΠ²Π°ΡΡ «ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ — Quicksort» .
ΠΡΠ½ΠΎΠ²Π½Π°Ρ ΠΈΠ΄Π΅Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠΎΠΌ, ΡΡΠΎ ΡΠ»ΡΡΠ°ΠΉΠ½ΡΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΠ²Π° x, ΠΏΠΎΡΠ»Π΅ ΡΠ΅Π³ΠΎ ΠΌΠ°ΡΡΠΈΠ² ΠΏΡΠΎΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΡΡΡ ΡΠ»Π΅Π²Π°, ΠΏΠΎΠΊΠ° Π½Π΅ Π²ΡΡΡΠ΅ΡΠΈΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ a[i] ΡΠ°ΠΊΠΎΠΉ, ΡΡΠΎ a[i] > x, Π° Π·Π°ΡΠ΅ΠΌ ΠΌΠ°ΡΡΠΈΠ² ΠΏΡΠΎΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΡΡΡ ΡΠΏΡΠ°Π²Π°, ΠΏΠΎΠΊΠ° Π½Π΅ Π²ΡΡΡΠ΅ΡΠΈΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ a[j] ΡΠ°ΠΊΠΎΠΉ, ΡΡΠΎ a[j] < x. ΠΡΠΈ Π΄Π²Π° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° ΠΌΠ΅Π½ΡΡΡΡΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ, ΠΈ ΠΏΡΠΎΡΠ΅ΡΡ ΠΏΡΠΎΡΠΌΠΎΡΡΠ°, ΡΡΠ°Π²Π½Π΅Π½ΠΈΡ ΠΈ ΠΎΠ±ΠΌΠ΅Π½Π° ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠ°Π΅ΡΡΡ, ΠΏΠΎΠΊΠ° ΠΌΡ Π½Π΅ Π΄ΠΎΠΉΠ΄Π΅ΠΌ Π΄ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° x. Π ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ² ΠΎΠΊΠ°ΠΆΠ΅ΡΡΡ ΡΠ°Π·Π±ΠΈΡΡΠΌ Π½Π° Π΄Π²Π΅ ΡΠ°ΡΡΠΈ — Π»Π΅Π²ΡΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΊΠ»ΡΡΠ΅ΠΉ Π±ΡΠ΄ΡΡ ΠΌΠ΅Π½ΡΡΠ΅ x, ΠΈ ΠΏΡΠ°Π²ΡΡ ΡΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌΠΈ ΠΊΠ»ΡΡΠ΅ΠΉ, Π±ΠΎΠ»ΡΡΠΈΠΌΠΈ x. ΠΠ°Π»Π΅Π΅ ΠΏΡΠΎΡΠ΅ΡΡ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠ°Π΅ΡΡΡ Π΄Π»Ρ Π»Π΅Π²ΠΎΠΉ ΠΈ ΠΏΡΠ°Π²ΠΎΠΉ ΡΠ°ΡΡΠ΅ΠΉ ΠΌΠ°ΡΡΠΈΠ²Π° Π΄ΠΎ ΡΠ΅Ρ ΠΏΠΎΡ, ΠΏΠΎΠΊΠ° ΠΊΠ°ΠΆΠ΄Π°Ρ ΡΠ°ΡΡΡ Π½Π΅ Π±ΡΠ΄Π΅Ρ ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΡ Π² ΡΠΎΡΠ½ΠΎΡΡΠΈ ΠΎΠ΄ΠΈΠ½ ΡΠ»Π΅ΠΌΠ΅Π½Ρ. ΠΠΎΠ½ΡΡΠ½ΠΎ, ΡΡΠΎ ΠΊΠ°ΠΊ ΠΎΠ±ΡΡΠ½ΠΎ, ΡΠ΅ΠΊΡΡΡΠΈΡ ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΌΠ΅Π½ΠΈΡΡ ΠΈΡΠ΅ΡΠ°ΡΠΈΡΠΌΠΈ, Π΅ΡΠ»ΠΈ Π·Π°ΠΏΠΎΠΌΠΈΠ½Π°ΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠ΅ ΠΈΠ½Π΄Π΅ΠΊΡΡ ΠΌΠ°ΡΡΠΈΠ²Π°. ΠΡΠΎΡΠ»Π΅Π΄ΠΈΠΌ ΡΡΠΎΡ ΠΏΡΠΎΡΠ΅ΡΡ Π½Π° ΠΏΡΠΈΠΌΠ΅ΡΠ΅ Π½Π°ΡΠ΅Π³ΠΎ ΡΡΠ°Π½Π΄Π°ΡΡΠ½ΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π° (ΡΠ°Π±Π»ΠΈΡΠ° 2.6).
Π’Π°Π±Π»ΠΈΡΠ° 6. ΠΡΠΈΠΌΠ΅Ρ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ.
ΠΠ°ΡΠ°Π»ΡΠ½ΠΎΠ΅ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π°. | 8 23 5 65 |44| 33 1 6. | |
Π¨Π°Π³ 1 (Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ x Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ a[5]). | |————|. 8 23 5 6 44 33 1 65. |—-|. 8 23 5 6 1 33 44 65. | |
Π¨Π°Π³ 2 (Π² ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Π΅ a[1], a[5] Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ x Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ a[3]). | 8 23 |5| 6 1 33 44 65. |————|. 1 23 5 6 8 33 44 65. |—|. 1 5 23 6 8 33 44 65. | |
Π¨Π°Π³ 3 (Π² ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Π΅ a[3], a[5] Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ x Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ a[4]). | 1 5 23 |6| 8 33 44 65. |——|. 1 5 8 6 23 33 44 65. | |
Π¨Π°Π³ 4 (Π² ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Π΅ a[3], a[4] Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ a[4]). | 1 5 8 |6| 23 33 44 65. |—|. 1 5 6 8 23 33 44 65. | |
ΠΠ»Π³ΠΎΡΠΈΡΠΌ Π½Π΅Π΄Π°ΡΠΎΠΌ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΎΠΉ, ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ Π΄Π»Ρ Π½Π΅Π³ΠΎ ΠΎΡΠ΅Π½ΠΊΠΎΠΉ ΡΠΈΡΠ»Π° ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ ΠΈ ΠΎΠ±ΠΌΠ΅Π½ΠΎΠ² ΡΠ²Π»ΡΠ΅ΡΡΡ O (n?log n). ΠΠ° ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅, Π² Π±ΠΎΠ»ΡΡΠΈΠ½ΡΡΠ²Π΅ ΡΡΠΈΠ»ΠΈΡ, Π²ΡΠΏΠΎΠ»Π½ΡΡΡΠΈΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ², ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ ΠΈΠΌΠ΅Π½Π½ΠΎ ΡΡΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ.
6. Π‘ΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ².
ΠΠ»Ρ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π±ΡΠ»Π° Π½Π°ΠΏΠΈΡΠ°Π½Π° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ°, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡΠ°Ρ Π²ΡΠΏΠΎΠ»Π½ΠΈΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ ΠΏΡΡΡΡ ΡΠΏΠΎΡΠΎΠ±Π°ΠΌΠΈ, ΠΏΠΎ Π²ΠΎΠ·ΡΠ°ΡΡΠ°Π½ΠΈΡ ΠΈΠ»ΠΈ ΡΠ±ΡΠ²Π°Π½ΠΈΡ. ΠΠ°ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π° ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡΡ ΡΠ»ΡΡΠ°ΠΉΠ½ΡΠΌΠΈ Π΄Π°Π½Π½ΡΠΌΠΈ.
Π ΠΈΡ 1. ΠΠ½ΡΠ΅ΡΡΠ΅ΠΉΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ.
ΠΠΎΡΠ»Π΅ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° Π²ΡΠ²ΠΎΠ΄ΠΈΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ ΠΈ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΎΠΊ. ΠΡΠΈ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΈ Π·Π°ΠΏΠΎΠ»Π½ΡΠ»Π°ΡΡ ΡΠ°Π±Π»ΠΈΡΠ° Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ ΡΠΈΡΠ»Π° ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΎΠΊ ΠΈ ΡΠΈΡΠ»Π° ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ ΠΎΡ ΡΠ°Π·ΠΌΠ΅ΡΠ° ΠΌΠ°ΡΡΠΈΠ²Π°.
Π’Π°Π±Π»ΠΈΡΠ° 7.
ΠΠ΅ΡΠΎΠ΄. | Π‘ΡΠ°Π²Π½Π΅Π½ΠΈΠΉ. | ΠΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΎΠΊ. | |||||||||
ΠΠΎΠ»-Π²ΠΎ. | |||||||||||
ΠΡΠ·ΡΡΡΠΊ. | |||||||||||
QuickSort. | |||||||||||
ΠΡΠ±ΠΎΡΠΎΠΌ. | |||||||||||
Π¨Π΅Π»Π»Π°. | |||||||||||
ΠΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ. | |||||||||||
ΠΠ° ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΈΠΈ Π΄Π°Π½Π½ΡΡ ΡΠ°Π±Π»ΠΈΡΡ Π±ΡΠ»ΠΈ ΠΏΠΎΡΡΡΠΎΠ΅Π½Ρ Π³ΡΠ°ΡΠΈΠΊΠΈ.
Π ΠΈΡ 2. ΠΠ°Π²ΠΈΡΠΈΠΌΠΎΡΡΡ ΡΠΈΡΠ»Π° ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΎΠΊ ΠΎΡ ΡΠ°Π·ΠΌΠ΅ΡΠ° ΠΌΠ°ΡΡΠΈΠ²Π° Π ΠΈΡ 3. ΠΠ°Π²ΠΈΡΠΈΠΌΠΎΡΡΡ ΡΠΈΡΠ»Π° ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ ΠΎΡ ΡΠ°Π·ΠΌΠ΅ΡΠ° ΠΌΠ°ΡΡΠΈΠ²Π°.
ΠΡΠ²ΠΎΠ΄Ρ.
ΠΠΎ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ°ΠΌ Π·Π°ΠΌΠ΅ΡΠΎΠ² ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°ΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ Π²ΡΠ²ΠΎΠ΄Ρ:
1. ΠΠ°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠ½ΠΈΠ²Π΅ΡΡΠ°Π»ΡΠ½ΡΠΌ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ, ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΌΠ΅ΡΠΎΠ΄ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ («QuickSort»), ΠΎΠ½ ΠΏΠΎΠΊΠ°Π·ΡΠ²Π°Π΅Ρ ΡΡΠ°Π±ΠΈΠ»ΡΠ½ΠΎ Π²ΡΡΠΎΠΊΠΈΠ΅ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ Π½Π° Π»ΡΠ±ΡΡ ΡΠ°Π·ΠΌΠ΅ΡΠ°Ρ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ². ΠΠ° Π²ΡΠΎΡΠΎΠΌ ΠΌΠ΅ΡΡΠ΅ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ ΠΌΠ΅ΡΠΎΠ΄ Π¨Π΅Π»Π»Π°. ΠΠ³ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΎΠ±ΠΎΡΠ½ΠΎΠ²Π°Π½ΠΎ Π±ΠΎΠ»ΡΡΠ΅Π΅ ΠΏΡΠΎΡΡΡΠΌ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠΌ Ρ ΡΠΎΡΠΊΠΈ Π·ΡΠ΅Π½ΠΈΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΡΠ°.
2. ΠΠ΅ΡΠΎΠ΄ Π²ΡΡΠ°Π²ΠΊΠΈ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π΅Π½, ΠΏΡΠΈ ΡΡΠ»ΠΎΠ²ΠΈΠΈ Π±ΠΎΠ»ΡΡΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΉ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ, ΡΠ°ΠΊ ΠΊΠ°ΠΊ ΠΎΠ½ ΡΠ²Π»ΡΠ΅ΡΡΡ Π°Π±ΡΠΎΠ»ΡΡΠ½ΡΠΌ Π»ΠΈΠ΄Π΅ΡΠΎΠΌ ΠΏΠΎ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΎΠΊ, ΠΏΡΠΎΠΈΠ³ΡΡΠ²Π°Ρ ΠΏΡΠΈ ΡΡΠΎΠΌ ΠΏΠΎ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ.
3. ΠΡΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ Π½Π΅Π±ΠΎΠ»ΡΡΠΈΡ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ² Π΄Π°Π½Π½ΡΡ Π½Π΅Ρ Π±ΠΎΠ»ΡΡΠΎΠΉ ΡΠ°Π·Π½ΠΈΡΡ ΠΏΠΎ ΡΠΊΠΎΡΠΎΡΡΠΈ ΠΌΠ΅ΠΆΠ΄Ρ ΠΌΠ΅ΡΠΎΠ΄Π°ΠΌΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΠΏΠΎΡΡΠΎΠΌΡ ΡΠ΅Π»Π΅ΡΠΎΠΎΠ±ΡΠ°Π·Π½Π΅Π΅ ΠΏΡΠΈΠΌΠ΅Π½ΡΡΡ ΠΌΠ΅ΡΠΎΠ΄ ΠΡΠ·ΡΡΡΠΊΠ° ΠΈΠ»ΠΈ ΠΌΠ΅ΡΠΎΠ΄ Π²ΡΡΠ°Π²ΠΎΠΊ.
4. ΠΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΡΠΎΠ²ΠΎΠ΄ΠΈΠ»ΠΎΡΡ Π½Π° ΠΌΠ°ΡΡΠΈΠ²Π°Ρ Ρ Π±ΠΎΠ»ΡΡΠΎΠΉ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ Π½Π΅ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΠΎΡΡΠΈ. ΠΠ»Ρ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ², ΠΊΠΎΡΠΎΡΡΠ΅ ΡΠΆΠ΅ ΡΠ²Π»ΡΡΡΡΡ ΠΏΠΎΡΡΠΈ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌΠΈ, Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΠΏΡΠΈΠΌΠ΅Π½ΠΈΠΌ ΠΌΠ΅ΡΠΎΠ΄ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ.
ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅.
ΠΠ»ΠΎΠΊ ΡΡ Π΅ΠΌΡ..
ΠΠ±ΠΌΠ΅Π½Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΡΠ°Π²ΠΊΠΎΠΉ.