Π Π΅ΡΠ°Ρ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΡΡ Π·Π°Π΄Π°ΡΡ, ΠΏΡΠΈΠΊΠ»Π°Π΄Π½Π°Ρ ΡΠΈΡΡΠ΅ΠΌΠ° ΠΠ ΠΏΠΎΠ»ΡΡΠ°Π΅Ρ Π½Π° Π²Ρ
ΠΎΠ΄Π΅ Π·Π½Π°Π½ΠΈΡ Π² ΡΠΎΠΉ ΠΈΠ»ΠΈ ΠΈΠ½ΠΎΠΉ ΡΠΎΡΠΌΠ΅, Π° Π½Π° Π²ΡΡ
ΠΎΠ΄Π΅ Π²ΡΠ΄Π°Π΅Ρ ΠΎΡΠ²Π΅Ρ, ΠΊΠΎΡΠΎΡΡΠΉ ΡΠ°ΠΊΠΆΠ΅ ΠΈΠΌΠ΅Π΅Ρ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΠΎΡΠΌΡ ΠΈ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅Ρ ΡΠΎΠ±ΠΎΠΉ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ΅ (Π½ΠΎΠ²ΠΎΠ΅) Π·Π½Π°Π½ΠΈΠ΅. Π ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΈΠΈ Ρ Π²Π²Π΅Π΄Π΅Π½Π½ΠΎΠΉ ΠΊΠ»Π°ΡΡΠΈΡΠΈΠΊΠ°ΡΠΈΠ΅ΠΉ Π²ΠΈΠ΄ΠΎΠ² Π·Π½Π°Π½ΠΈΠΉ ΠΈΡΠΊΡΡΡΡΠ²Π΅Π½Π½ΠΎΠΈΠ½ΡΠ΅Π»Π»Π΅ΠΊΡΡΠ°Π»ΡΠ½ΡΠ΅ ΡΠΈΡΡΠ΅ΠΌΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΊΠ»Π°ΡΡΠΈΡΠΈΡΠΈΡΠΎΠ²Π°ΡΡ ΠΏΠΎ ΡΡΠΎΠ²Π½Ρ Π²ΡΠ΄Π°Π²Π°Π΅ΠΌΠΎΠ³ΠΎ ΠΎΡΠ²Π΅ΡΠ°.
- 1. ΠΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΎΡΠ²Π΅Ρ (Π΄Π° ΠΈΠ»ΠΈ Π½Π΅Ρ) — Π½Π΅ ΠΎΡΠ΅Π½Ρ ΡΠ΄ΠΎΠ±Π½Ρ Π² ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ, ΡΠ΅ΠΉΡΠ°Ρ ΠΏΡΠΈΠΌΠ΅Π½ΡΡΡΡΡ ΡΠ΅Π΄ΠΊΠΎ.
- 2. Π€Π°ΠΊΡΠΎΠ³ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΎΡΠ²Π΅Ρ (ΠΎΡΠ²Π΅Ρ-ΡΠ°ΠΊΡ); Π΅ΡΠ»ΠΈ Π²ΡΠ΄Π°Π΅ΡΡΡ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΡΠΉ ΠΎΡΠ²Π΅Ρ Π½Π° ΠΎΠ΄ΠΈΠ½ Π²ΠΎΠΏΡΠΎΡ, ΡΠΎ ΡΠ°ΠΊΠΈΠ΅ ΡΠΈΡΡΠ΅ΠΌΡ ΡΠ°ΡΡΠΎ Π½Π°Π·ΡΠ²Π°ΡΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΎΠ½Π½ΡΠΌΠΈ ΡΠΈΡΡΠ΅ΠΌΠ°ΠΌΠΈ. Π Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΡΠ°ΡΠΏΡΠΎΡΡΡΠ°Π½Π΅Π½Π½ΡΠΉ ΠΊΠ»Π°ΡΡ ΡΠΈΡΡΠ΅ΠΌ.
- 3. ΠΡΠΎΡΠ΅Π΄ΡΡΠ½ΡΠΉ ΠΎΡΠ²Π΅Ρ — ΡΠ΅ΡΠ°Ρ Π·Π°Π΄Π°ΡΡ, ΡΠΈΡΡΠ΅ΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ ΡΠΎΠ·Π΄Π°ΡΡ ΠΈ Π·Π°ΠΏΡΡΡΠΈΡΡ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ (ΡΠΈΡΡΠ΅ΠΌΠ° ΡΠΈΠ½ΡΠ΅Π·Π° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌ, Π°Π²ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅). ΠΡΠ΅Π½Ρ ΠΈΠ½ΡΠ΅ΡΠ΅ΡΠ½ΠΎΠ΅ ΠΈ ΠΏΠ΅ΡΡΠΏΠ΅ΠΊΡΠΈΠ²Π½ΠΎΠ΅ Π½Π°ΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠ΅, ΠΏΡΠΈΠ²Π»Π΅ΠΊΠ°ΡΡΠ΅Π΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π±ΠΎΠ»ΡΡΠΎΠ³ΠΎ ΡΠΈΡΠ»Π° ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»Π΅ΠΉ (ΡΠΌ. Π³Π». 5).
- 4. ΠΠΎΠ½ΡΡΠΈΠΉΠ½ΡΠΉ ΠΎΡΠ²Π΅Ρ — ΠΎΡΠ²Π΅Ρ-Π·Π°ΠΊΠΎΠ½, ΡΡΡΠΎΠΈΡΡΡ Π½Π΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅, Π° ΡΡ
Π΅ΠΌΠ° ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΊΠ»Π°ΡΡΠ° Π·Π°Π΄Π°Ρ, ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π½Π΅ Π²ΡΠΏΠΎΠ»Π½ΠΈΠΌΠ° Π΄Π°ΠΆΠ΅ Π½Π° ΠΊΠΎΠΌΠΏΡΡΡΠ΅ΡΠ΅. Π Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ ΠΏΠΎΠ»Π½ΠΎΠΌΠ°ΡΡΡΠ°Π±Π½ΡΠ΅ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΏΠΎΠΊΠ° Π½Π΅ΠΈΠ·Π²Π΅ΡΡΠ½Ρ1.
ΠΡΠΈΠ²Π΅Π΄Π΅ΠΌ ΠΏΡΠΈΠΌΠ΅ΡΡ ΠΎΡΠ²Π΅ΡΠΎΠ² ΡΠ°Π·Π½ΡΡ
ΡΡΠΎΠ²Π½Π΅ΠΉ, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ ΠΌΠΎΠ΄Π΅Π»ΡΠ½ΡΠΉ ΠΏΡΠΈΠΌΠ΅Ρ Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΎΠΉ ΡΠΈΡΠ΅Π» ΠΈΠ· ΠΏ. 1.2.2 (Π½Π°ΠΏΠΎΠΌΠ½ΠΈΠΌ, Π·Π°Π΄Π°ΡΠ° ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ: ΠΌΡ Ρ
ΠΎΡΠΈΠΌ, ΡΡΠΎΠ±Ρ ΠΊΠΎΠΌΠΏΡΡΡΠ΅Ρ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π» Π½Π°Π±ΠΎΡ ΠΈΠ· ΡΡΠ΅Ρ
ΡΠΈΡΠ΅Π» Π² ΠΏΠΎΡΡΠ΄ΠΊΠ΅ ΠΈΡ
Π²ΠΎΠ·ΡΠ°ΡΡΠ°Π½ΠΈΡ).
Π£ΡΠΎΠ²Π΅Π½Ρ 0: 3 5 7—" Π΄Π°.
5 3 7 —" Π½Π΅Ρ Π£ΡΠΎΠ²Π΅Π½Ρ 1: 5 3 7 —" 2 3 7.
Π£ΡΠΎΠ²Π΅Π½Ρ 2 {Ρ
7 Π³/, z}?{x <οΏ½Ρ < Π³} —" Sort3.
Π£ΡΠΎΠ²Π΅Π½Ρ 3 (Π³,) ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ —" V i9j (i —" Ρ
{ < Ρ
})
ΠΠ° ΡΡΠΎΠ²Π½Π΅ 0 ΠΌΡ ΠΏΡΠ΅Π΄ΡΡΠ²Π»ΡΠ΅ΠΌ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ, Π° ΡΠΈΡΡΠ΅ΠΌΠ° ΡΠΎΠ»ΡΠΊΠΎ ΠΏΡΠΎΠ²Π΅ΡΡΠ΅Ρ, ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π° ΠΎΠ½Π° ΠΈΠ»ΠΈ Π½Π΅Ρ. ΠΠ° ΡΡΠΎΠ²Π½Π΅ 1 ΠΌΡ ΠΏΡΠ΅Π΄ΡΡΠ²Π»ΡΠ΅ΠΌ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ, ΠΈ ΡΠΈΡΡΠ΅ΠΌΠ° Π΅Π΅ ΠΏΠΎΡΠ»ΡΡΠ½ΠΎ ΡΠΎΡΡΠΈΡΡΠ΅Ρ. ΠΠ° ΡΡΠΎΠ²Π½Π΅ 2 ΡΠΈΡΡΠ΅ΠΌΠ° ΡΡΡΠΎΠΈΡ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠΈΠΌΠ΅ΡΠ½ΠΎ ΡΠ°ΠΊ, ΠΊΠ°ΠΊ ΡΡΠΎ ΠΏΠΎΠΊΠ°Π·Π°Π½ΠΎ Π² ΠΈ. 1.2.2. ΠΠ°ΠΊΠΎΠ½Π΅Ρ, Π½Π° ΡΡΠΎΠ²Π½Π΅ 3 Π³ΠΈΠΏΠΎΡΠ΅ΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΡΠΈΡΡΠ΅ΠΌΠ° ΠΎΠ±ΡΡΡΠ½ΡΠ΅Ρ Π½Π°ΠΌ, ΡΡΠΎ ΡΡΠΎ Π·Π½Π°ΡΠΈΡ — ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΠ² ΡΠΈΡΠ΅Π»[1][2].
- [1] Π£ ΠΈΡΠΊΡΡΡΡΠ²Π΅Π½Π½ΠΎΠ³ΠΎ ΠΈΠ½ΡΠ΅Π»Π»Π΅ΠΊΡΠ° Π΅ΡΡΡ, ΠΊ ΡΠΎΠΆΠ°Π»Π΅Π½ΠΈΡ, Π·Π°ΡΠ΅ΠΊΡΠ΅ΡΠ΅Π½Π½Π°Ρ ΠΎΠ±Π»Π°ΡΡΡ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΡ —Π±ΠΎΠ΅Π²ΡΠ΅ ΡΠΎΠ±ΠΎΡΡ ΠΈ ΡΠΈΡΡΠ΅ΠΌΡ. ΠΡ Π½ΠΈΡΠ΅Π³ΠΎ ΠΎΠ± ΡΡΠΎΠΌ Π½Π΅ Π·Π½Π°Π΅ΠΌ ΠΈ Π½ΠΈΠΊΠ°ΠΊΠΈΡ
ΠΏΡΠΈΠΌΠ΅ΡΠΎΠ² Π½Π΅ ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌ, Π½ΠΎ Π΄ΠΎΠΏΡΡΠΊΠ°Π΅ΠΌ, ΡΡΠΎ Π² ΡΡΠΎΠΉ ΠΎΠ±Π»Π°ΡΡΠΈ ΠΌΠΎΠ³ΡΡ Π±ΡΡΡ Π½Π΅ΠΈΠ·Π²Π΅ΡΡΠ½ΡΠ΅ Π½Π°ΠΌ Π΄ΠΎΡΡΠΈΠΆΠ΅Π½ΠΈΡ.
- [2] Π Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΡ, ΠΊΠΎΡΠΎΡΠ°Ρ ΠΌΠΎΠ³Π»Π° Π±Ρ Π΄Π°ΡΡ ΠΎΡΠ²Π΅Ρ Π½Π° Π²ΠΎΠΏΡΠΎΡ, «ΡΡΠΎΠ·Π½Π°ΡΠΈΡ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΠ²?», Π²ΠΈΠ΄ΠΈΠΌΠΎ, Π½Π΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ. ΠΠ΄Π½Π°ΠΊΠΎ, ΠΊΠ°ΠΊ Π²Π΅Π»ΠΈΠΊΠ° Π΄ΠΎΠ»Ρ Π»ΡΠ΄Π΅ΠΉ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΌΠΎΠ³ΡΡ Π΄Π°ΡΡ ΠΎΡΠ²Π΅Ρ Π½Π° ΡΡΠΎΡ Π²ΠΎΠΏΡΠΎΡ, Π½Π΅ ΠΏΡΠΈΠ±Π΅Π³Π°Ρ ΠΊ ΠΏΠΎΠΌΠΎΡΠΈ ΠΆΠ΅ΡΡΠΎΠ² ΠΈ ΠΏΡΠΈΠΌΠ΅ΡΠΎΠ²?