Farididdin Rahimov 15 дСкабря 2021

πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

ОсваиваСм основы Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΠΎΡ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ΡΡ Π»ΡŽΠ±ΠΎΠΌΡƒ Π½Π°Ρ‡ΠΈΠ½Π°ΡŽΡ‰Π΅ΠΌΡƒ программисту Π½Π° C++ (ΠΈ Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ). АдСкватноС прСдставлСниС ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния ΠΊΠΎΠ΄Π° ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ Ρ€Π΅ΡˆΠ°ΡŽΡ‰ΠΈΠΌ Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΎΠΌ Ρ‚Π°ΠΌ, Π³Π΄Π΅ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ ΠΈΠΌΠ΅Π΅Ρ‚ большоС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅.
πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

Если Ρ…ΠΎΡ‡Π΅ΡˆΡŒ ΠΏΠΎΠ΄Ρ‚ΡΠ½ΡƒΡ‚ΡŒ свои знания, загляни Π½Π° наш курс «Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…Β», Π½Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Ρ‚Ρ‹:

  1. ΡƒΠ³Π»ΡƒΠ±ΠΈΡˆΡŒΡΡ Π² Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ практичСских Π·Π°Π΄Π°Ρ‡;
  2. ΡƒΠ·Π½Π°Π΅ΡˆΡŒ всС ΠΏΡ€ΠΎ слоТныС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹, сортировки, сТатиС Π΄Π°Π½Π½Ρ‹Ρ… ΠΈ ΠΌΠ½ΠΎΠ³ΠΎΠ΅ Π΄Ρ€ΡƒΠ³ΠΎΠ΅.

Π’Ρ‹ Ρ‚Π°ΠΊΠΆΠ΅ Π±ΡƒΠ΄Π΅ΡˆΡŒ Π½Π° связи с ΠΏΡ€Π΅ΠΏΠΎΠ΄Π°Π²Π°Ρ‚Π΅Π»Π΅ΠΌ ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠΌΠΈ студСнтами.

Π’ ΠΈΡ‚ΠΎΠ³Π΅ Π±ΡƒΠ΄Π΅ΡˆΡŒ Π±Ρ€Π°Ρ‚ΡŒΡΡ Π·Π° слоТныС ΠΏΡ€ΠΎΠ΅ΠΊΡ‚Ρ‹ ΠΈ ΠΏΠΎΠ²Ρ‹ΡΠΈΡˆΡŒ Ρ‡Π΅ΠΊ Π·Π° свою Ρ€Π°Π±ΠΎΡ‚Ρƒ πŸ™‚

***
ЦСль Ρ†ΠΈΠΊΠ»Π°
Π­Ρ‚ΠΎΡ‚ Ρ†ΠΈΠΊΠ» статСй прСдставляСт собой ΠΊΡ€Π°Ρ‚ΠΊΠΎΠ΅ Π²Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π² Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…. Π‘ΡƒΠ΄ΡƒΡ‡ΠΈ ΠΊΡ€Π°Ρ‚ΠΊΠΈΠΌ руководством, ΠΎΠ½ Π½Π΅ являСтся ΠΈΡΡ‡Π΅Ρ€ΠΏΡ‹Π²Π°ΡŽΡ‰ΠΈΠΌ пособиСм, Π° ΠΎΡ…Π²Π°Ρ‚Ρ‹Π²Π°Π΅Ρ‚ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ самыС Π²Π°ΠΆΠ½Ρ‹Π΅ Ρ‚Π΅ΠΌΡ‹. ЦСлСвая аудитория – Ρ‡ΠΈΡ‚Π°Ρ‚Π΅Π»ΠΈ, ΠΆΠ΅Π»Π°ΡŽΡ‰ΠΈΠ΅ ΡƒΠ·Π½Π°Ρ‚ΡŒ ΠΎΠ± Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°Ρ…, Π½ΠΎ Π½Π΅ ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΠ΅ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ Π½Π° Ρ‡Ρ‚Π΅Π½ΠΈΠ΅ ΠΊΠ½ΠΈΠ³, Π³Π»ΡƒΠ±ΠΎΠΊΠΎ ΠΎΡΠ²Π΅Ρ‰Π°ΡŽΡ‰ΠΈΡ… этот ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚. НапримСр, сСрия Π΄ΠΎΠ»ΠΆΠ½Π° Π·Π°ΠΈΠ½Ρ‚Π΅Ρ€Π΅ΡΠΎΠ²Π°Ρ‚ΡŒ Ρ‡ΠΈΡ‚Π°Ρ‚Π΅Π»Π΅ΠΉ, готовящихся ΠΊ прСдстоящСму собСсСдованию. Π‘Ρ‚Π°Ρ‚ΡŒΠΈ Π½Π΅ Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ ΠΎΡ‚ читатСля ΠΏΡ€Π΅Π΄Π²Π°Ρ€ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ ΠΏΠΎΠ΄Π³ΠΎΡ‚ΠΎΠ²ΠΊΠΈ, ΡΠ²ΡΠ·Π°Π½Π½ΡƒΡŽ с Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌΠΈ ΠΈ структурами Π΄Π°Π½Π½Ρ‹Ρ…, Π½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½Ρ‹Π΅ знания Π² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ Π½Π° C++ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΡ‹.

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ?

Алгоритм – это ΡΠΎΠ²ΠΎΠΊΡƒΠΏΠ½ΠΎΡΡ‚ΡŒ Ρ‡Π΅Ρ‚ΠΊΠΎ сформулированных инструкций, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Ρ€Π΅ΡˆΠ°ΡŽΡ‚ Ρ‚ΠΎΡ‡Π½ΠΎ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½Π½ΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ, Ссли ΠΈΠΌ ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚ΡŒ. Π—Π΄Π΅ΡΡŒ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ Π·Π°Π΄Π°Ρ‡ΠΈ ΠΏΠΎΠ΄Ρ€Π°Π·ΡƒΠΌΠ΅Π²Π°Π΅Ρ‚ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… Π² ΠΆΠ΅Π»Π°Π΅ΠΌΡ‹ΠΉ ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹ΠΉ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚. К ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρƒ, сортировка – это Π·Π°Π΄Π°Ρ‡Π° упорядочивания ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ чисСл Π² порядкС возрастания. Π‘ΠΎΠ»Π΅Π΅ Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎ ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ эту ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡƒ Π² Π²ΠΈΠ΄Π΅ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… ΠΈ Π²Ρ‹Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…: Π²Ρ…ΠΎΠ΄Π½Ρ‹ΠΌΠΈ Π΄Π°Π½Π½Ρ‹ΠΌΠΈ являСтся любая ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ чисСл, Π° Π²Ρ‹Ρ…ΠΎΠ΄Π½Ρ‹ΠΌΠΈ – пСрСстановка Π²Ρ…ΠΎΠ΄Π½ΠΎΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ мСньшиС элСмСнты Ρ€Π°ΡΠΏΠΎΠ»Π°Π³Π°ΡŽΡ‚ΡΡ ΠΏΠ΅Ρ€Π΅Π΄ большими. Алгоритм ΠΌΠΎΠΆΠ½ΠΎ ΡΡ‡ΠΈΡ‚Π°Ρ‚ΡŒ ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½Ρ‹ΠΌ, Ссли для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΈΠ· Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… ΠΎΠ½ Π΄Π°Π΅Ρ‚ ΠΆΠ΅Π»Π°Π΅ΠΌΡ‹ΠΉ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚. Алгоритм Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½Ρ‹ΠΌ, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ инструкции Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ понятными ΠΈ ΠΈΠΌΠ΅Ρ‚ΡŒ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ СдинствСнноС Ρ‚ΠΎΠ»ΠΊΠΎΠ²Π°Π½ΠΈΠ΅. Алгоритм Ρ‚Π°ΠΊΠΆΠ΅ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒΡΡ бСсконСчно ΠΈ Π·Π°Π²Π΅Ρ€ΡˆΠ°Ρ‚ΡŒΡΡ послС ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ³ΠΎ числа дСйствий.

Π’Π°ΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅ Ρ‚Ρ€ΡƒΠ΄Π½ΠΎ ΠΏΠ΅Ρ€Π΅ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ. Они ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ программисту Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Ρ‚ΡŒ эффСктивныС, Π½Π°Π΄Π΅ΠΆΠ½Ρ‹Π΅ ΠΈ быстрыС Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π° ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΠΉ ΠΏΡ€ΠΎΠΌΠ΅ΠΆΡƒΡ‚ΠΎΠΊ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ. ΠŸΠΎΡ‡Ρ‚ΠΈ Π»ΡŽΠ±Ρ‹Π΅ слоТныС ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Π½Π° соврСмСнных ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€Π°Ρ… Π² Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ стСпСни ΠΎΠΏΠΈΡ€Π°ΡŽΡ‚ΡΡ Π½Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹. ΠžΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΎΠ½Π½Ρ‹Π΅ систСмы ΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌΠΈ планирования, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΎΡ€Π³Π°Π½ΠΈΠ·ΡƒΡŽΡ‚ ΠΈ Ρ€Π°ΡΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‚ процСссорноС врСмя ΠΌΠ΅ΠΆΠ΄Ρƒ процСссами, создавая иллюзию, Ρ‡Ρ‚ΠΎ ΠΎΠ½ΠΈ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ. МногиС ΡƒΠΌΠ½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹, Ρ‚Π°ΠΊΠΈΠ΅ ΠΊΠ°ΠΊ растСризация, отсСчСниС, back-face culling ΠΈ сглаТиваниС, слуТат для создания ΠΏΠΎΡ‚Ρ€ΡΡΠ°ΡŽΡ‰ΠΈΡ… 3D-ΠΌΠΈΡ€ΠΎΠ² Π² Ρ€Π΅Π°Π»ΡŒΠ½ΠΎΠΌ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ. Алгоритмы ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ Π½Π°ΠΉΡ‚ΠΈ ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠΈΠΉ ΠΌΠ°Ρ€ΡˆΡ€ΡƒΡ‚ ΠΊ мСсту назначСния Π² Π³ΠΎΡ€ΠΎΠ΄Π΅, содСрТащСм тысячи ΡƒΠ»ΠΈΡ†. Благодаря Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌ машинного обучСния ΠΏΡ€ΠΎΠΈΠ·ΠΎΡˆΠ»Π° Ρ€Π΅Π²ΠΎΠ»ΡŽΡ†ΠΈΡ Π² Ρ‚Π°ΠΊΠΈΡ… областях, ΠΊΠ°ΠΊ распознаваниС ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ ΠΈ Ρ€Π΅Ρ‡ΠΈ. ΠŸΠ΅Ρ€Π΅Ρ‡ΠΈΡΠ»Π΅Π½Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ – это Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½Π° айсбСрга, ΠΈ ΠΈΠ·ΡƒΡ‡Π΅Π½ΠΈΠ΅ этого ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚Π° ΠΎΡ‚ΠΊΡ€ΠΎΠ΅Ρ‚ мноТСство Π΄Π²Π΅Ρ€Π΅ΠΉ Π² ΠΊΠ°Ρ€ΡŒΠ΅Ρ€Π΅ программиста.

Π‘ΠΎΠ»ΡŒΡˆΠ΅ ΠΏΠΎΠ»Π΅Π·Π½ΠΎΠΉ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ Π²Ρ‹ Π½Π°ΠΉΠ΄Π΅Ρ‚Π΅ Π½Π° нашСм Ρ‚Π΅Π»Π΅Π³Ρ€Π°ΠΌ-ΠΊΠ°Π½Π°Π»Π΅ Β«Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° программиста».

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°

НачнСм ΠΌΡ‹ нашС ΠΏΡƒΡ‚Π΅ΡˆΠ΅ΡΡ‚Π²ΠΈΠ΅ Π² ΠΌΠΈΡ€ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² со знакомства с Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ называСтся сортировкой вставками. Π”Π°Π½Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ являСтся ΠΎΠ΄Π½ΠΈΠΌ ΠΈΠ· ΠΌΠ½ΠΎΠ³ΠΈΡ… ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Ρ€Π°Π½Π΅Π΅ упомянутой Π·Π°Π΄Π°Ρ‡ΠΈ сортировки. Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° вставкой Π²ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΌ Π½Π°ΠΏΠΎΠΌΠΈΠ½Π°Π΅Ρ‚ Ρ‚ΠΎ, ΠΊΠ°ΠΊ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΡΠΎΡ€Ρ‚ΠΈΡ€ΡƒΡŽΡ‚ ΠΊΠ°Ρ€Ρ‚Ρ‹ Π² своих Ρ€ΡƒΠΊΠ°Ρ…. ΠŸΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΠΌ, Ρ‡Ρ‚ΠΎ Ρƒ нас Π² Ρ€ΡƒΠΊΠ΅ ΠΈΠΌΠ΅ΡŽΡ‚ΡΡ ΠΊΠ°Ρ€Ρ‚Ρ‹, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΡƒΠΆΠ΅ отсортированы. Когда ΠΊΡ€ΡƒΠΏΡŒΠ΅ ΠΏΠ΅Ρ€Π΅Π΄Π°Π΅Ρ‚ Π½Π°ΠΌ Π½ΠΎΠ²ΡƒΡŽ ΠΊΠ°Ρ€Ρ‚Ρƒ, ΠΌΡ‹ сразу ΠΊΠ»Π°Π΄Π΅ΠΌ Π΅Π΅ Π² ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΊΠ°Ρ€Ρ‚Ρ‹ ΠΎΡΡ‚Π°Π²Π°Π»ΠΈΡΡŒ отсортированными. ΠœΡ‹ повторяСм это Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° всС ΠΊΠ°Ρ€Ρ‚Ρ‹ Π½Π΅ Π±ΡƒΠ΄ΡƒΡ‚ сданы. ΠšΠΎΠ½Ρ†Π΅ΠΏΡ‚ΡƒΠ°Π»ΡŒΠ½ΠΎ сортировка вставкой Π΄Π΅Π»ΠΈΡ‚ массив Π½Π° Π΄Π²Π΅ части: ΠΎΡ‚ΡΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΡƒΡŽ ΠΈ Π½Π΅ΠΎΡ‚ΡΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΡƒΡŽ. ΠŸΠΎΠ½Π°Ρ‡Π°Π»Ρƒ отсортированная Ρ‡Π°ΡΡ‚ΡŒ состоит Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΈΠ· ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ элСмСнта массива, Π° ΠΎΡΡ‚Π°Π»ΡŒΠ½Π°Ρ Π΅Π³ΠΎ Ρ‡Π°ΡΡ‚ΡŒ Π½Π΅ отсортирована. Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° вставками Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΈΠ·Π²Π»Π΅ΠΊΠ°Π΅Ρ‚ ΠΎΠ΄ΠΈΠ½ элСмСнт ΠΈΠ· нСсортированной части, опрСдСляСт Π΅Π³ΠΎ мСстополоТСниС Π² отсортированном спискС ΠΈ вставляСт Π΅Π³ΠΎ Ρ‚ΡƒΠ΄Π°. Π­Ρ‚ΠΎΡ‚ процСсс продолТаСтся Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π² нСсортированной части Π½Π΅ останСтся Π½ΠΈ ΠΎΠ΄Π½ΠΎΠ³ΠΎ элСмСнта. Визуализация сортировки вставками:

πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²
πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²
πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²
πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²
πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²
πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²
πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

Π—Π΄Π΅ΡΡŒ отсортированный подмассив Π²Ρ‹Π΄Π΅Π»Π΅Π½ синим Ρ†Π²Π΅Ρ‚ΠΎΠΌ. Данная Π΄ΠΈΠ°Π³Ρ€Π°ΠΌΠΌΠ° Π½Π΅ ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚, ΠΊΠ°ΠΊ ΠΈΠΌΠ΅Π½Π½ΠΎ сортировка вставками ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Ρ‰Π°Π΅Ρ‚ элСмСнты ΠΈΠ· нСсортированного подмассива Π² сортированный. Она вставляСт элСмСнт Π² отсортированный подмассив ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ:

  • БохраняСт Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ элСмСнта Π²ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ;
  • ΠŸΠ΅Ρ€Π΅ΠΌΠ΅Ρ‰Π°Π΅Ρ‚ всС элСмСнты, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ большС Ρ‡Π΅ΠΌ вставляСмый элСмСнт (располоТСнныС ΠΏΠ΅Ρ€Π΅Π΄ этим элСмСнтом) Π½Π° ΠΎΠ΄Π½ΠΎ мСсто Π²ΠΏΡ€Π°Π²ΠΎ;
  • ΠŸΠΎΠΌΠ΅Ρ‰Π°Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π² освободившССся мСсто.

Π”Π°Π²Π°ΠΉΡ‚Π΅ ΠΏΠΎΠ΄Ρ€ΠΎΠ±Π½Π΅Π΅ рассмотрим этот процСсс Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅:

πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

Π—Π΄Π΅ΡΡŒ, СдинствСнный элСмСнт, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΎΡΡ‚Π°Π»ΠΎΡΡŒ Π²ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π² отсортированный подмассив – это 4. ΠœΡ‹ сохраняСм это Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π²ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΡŽ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ.

πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

ΠœΡ‹ сравниваСм 4 с 7, ΠΈ ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ 7 большС, ΠΌΡ‹ ΠΊΠΎΠΏΠΈΡ€ΡƒΠ΅ΠΌ Π΅Π³ΠΎ Π½Π° ΠΏΠΎΠ·ΠΈΡ†ΠΈΡŽ справа (значСния, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΡ‹ сравниваСм с вставляСмым элСмСнтом, ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½Ρ‹ Ρ„ΠΈΠΎΠ»Π΅Ρ‚ΠΎΠ²Ρ‹ΠΌ).

πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

Π‘Ρ€Π°Π²Π½ΠΈΠ²Π°Π΅ΠΌ 4 с 6, ΠΈ ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ 6 большС, ΠΊΠΎΠΏΠΈΡ€ΡƒΠ΅ΠΌ Π΅Π³ΠΎ Π½Π° ΠΏΠΎΠ·ΠΈΡ†ΠΈΡŽ справа.

πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

Π‘Ρ€Π°Π²Π½ΠΈΠ²Π°Π΅ΠΌ 4 с 5, Π° ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ 5 Ρ‚ΠΎΠΆΠ΅ большС Ρ‡Π΅ΠΌ 4, Π΅Π³ΠΎ Ρ‚ΠΎΠΆΠ΅ ΠΊΠΎΠΏΠΈΡ€ΡƒΠ΅ΠΌ Π΅Π³ΠΎ Π½Π° ΠΏΠΎΠ·ΠΈΡ†ΠΈΡŽ справа.

πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

НаконСц, ΠΌΡ‹ сравниваСм 4 с 3, ΠΈ Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ 3 мСньшС Ρ‡Π΅ΠΌ 4, ΠΌΡ‹ присваиваСм Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π½Π° ΠΏΠΎΠ·ΠΈΡ†ΠΈΡŽ рядом с Π½ΠΈΠΌ. И Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ наша Ρ€Π°Π±ΠΎΡ‚Π° Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½Π°; ΠΌΡ‹ располоТили 4 Π² ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅.

Как ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ, программисты ΠΎΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π² Π²ΠΈΠ΄Π΅ псСвдокода. ПсСвдокод – это Π½Π΅Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ способ описания Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ‚ строгого синтаксиса, свойствСнного языкам программирования ΠΈ Π½Π΅ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ соблюдСния тСхнологичСских сообраТСний. ΠŸΡ€ΠΈΠ²Π΅Π΄Π΅ΠΌ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ псСвдокода сортировки вставками:

PseudocodeInsertionSort
        n ← Array.size
For i=2 to n
    j ← i – 1
    temp ← Array[j]
    While Array[j-1]>temp and j>0
        Array[j] ← Array[j-1];
        j ← j-1
    Array[j] ← temp

    

НаписаниС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π² псСвдокодС ΠΏΠΎΡ€ΠΎΠΉ Π±Ρ‹Π²Π°Π΅Ρ‚ ΠΏΠΎΠ»Π΅Π·Π½Ρ‹ΠΌ, Π½ΠΎ ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ эти ΡΡ‚Π°Ρ‚ΡŒΠΈ посвящСны Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌ Π½Π° C++, Π² дальнСйшСм ΠΌΡ‹ сосрСдоточимся Π½Π° Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° C++. ΠŸΡ€ΠΈΠΌΠ΅Ρ€ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Π½Π° C++, которая Ρ€Π΅Π°Π»ΠΈΠ·ΡƒΠ΅Ρ‚ сортировку вставками:

InsertionSort.cpp
        void insertionSort(int *array, int n)
{
    for(int i=2;i<=n;++i)
    {
        int j=i-1;
        int temp = array[j];
        while(array[j-1]>temp)
        {
            array[j]=array[j-1];
            --j;
        }
        array[j]=temp;
    }
}

    

ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π°

Π Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π² Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ, Π½Π°ΠΌ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ, сколько рСсурсов, Ρ‚Π°ΠΊΠΈΡ… ΠΊΠ°ΠΊ врСмя ΠΈ ΠΏΠ°ΠΌΡΡ‚ΡŒ, ΠΎΠ½ потрСбляСт. Π’Π΅Π΄ΡŒ Ссли Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ΡΡ Π³ΠΎΠ΄Ρ‹ для получСния ΠΏΡ€Π°Π²ΠΈΠ»ΡŒΠ½ΠΎΠ³ΠΎ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π° ΠΈΠ»ΠΈ ΠΎΠ½ Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ‚ сотни Ρ‚Π΅Ρ€Π°Π±Π°ΠΉΡ‚, Ρ‚ΠΎ Π½Π° ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅ ΠΎΠ½ Π½Π΅ΠΏΡ€ΠΈΠ³ΠΎΠ΄Π΅Π½. Π’Π°ΠΊΠΆΠ΅, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹, Ρ€Π΅ΡˆΠ°ΡŽΡ‰ΠΈΠ΅ ΠΎΠ΄Π½Ρƒ ΠΈ Ρ‚Ρƒ ΠΆΠ΅ Π·Π°Π΄Π°Ρ‡Ρƒ, ΠΌΠΎΠ³ΡƒΡ‚ ΠΏΠΎΡ‚Ρ€Π΅Π±Π»ΡΡ‚ΡŒ Ρ€Π°Π·Π½ΠΎΠ΅ количСство рСсурсов Π² зависимости ΠΎΡ‚ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…, поэтому ΠΏΡ€ΠΈ Π²Ρ‹Π±ΠΎΡ€Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌ Ρ‚Ρ‰Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ Π°Π½Π°Π»ΠΈΠ·.

ΠŸΡ€ΠΈ ΠΈΠ·ΡƒΡ‡Π΅Π½ΠΈΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² ΠΌΡ‹ Ρ€Π΅Π΄ΠΊΠΎ ΠΎΠ±Ρ€Π°Ρ‰Π°Π΅ΠΌ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π½Π° Π΄Π΅Ρ‚Π°Π»ΠΈ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ языков программирования ΠΈ ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€ΠΎΠ². Учитывая, насколько быстро развиваСтся ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€Π½Π°Ρ индустрия, Ρ‚Π°ΠΊΠΈΠ΅ Π΄Π΅Ρ‚Π°Π»ΠΈ постоянно ΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ. Π‘ Π΄Ρ€ΡƒΠ³ΠΎΠΉ стороны, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ сами ΠΏΠΎ сСбС нСподвластны Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ. Π‘Π»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, Π½Π°ΠΌ Π½ΡƒΠΆΠ΅Π½ ΠΌΠ΅Ρ‚ΠΎΠ΄ ΠΎΡ†Π΅Π½ΠΊΠΈ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π² нСзависимости ΠΎΡ‚ ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€Π°, Π½Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ ΠΎΠ½ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚. Π”Π²Π° основных срСдства, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Π΅ Π½Π°ΠΌΠΈ для этой Ρ†Π΅Π»ΠΈ, это – абстрактная модСль ΠΌΠ°ΡˆΠΈΠ½Ρ‹ (ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€Π°) ΠΈ асимптотичСский Π°Π½Π°Π»ΠΈΠ·.

Абстрактная модСль ΠΌΠ°ΡˆΠΈΠ½Ρ‹

Π’ процСссС Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² ΠΌΡ‹ прСдставляСм, Ρ‡Ρ‚ΠΎ выполняСм ΠΈΡ… Π½Π° простой гипотСтичСской ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€Π½ΠΎΠΉ ΠΌΠΎΠ΄Π΅Π»ΠΈ. Как ΠΈ всС соврСмСнныС ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€Ρ‹, наша модСль выполняСт инструкции ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ. МодСль ΠΏΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΈΠ²Π°Π΅Ρ‚ ряд простых ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ, Ρ‚Π°ΠΊΠΈΡ… ΠΊΠ°ΠΊ слоТСниС, Π²Ρ‹Ρ‡ΠΈΡ‚Π°Π½ΠΈΠ΅, ΡƒΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅, присвоСниС, сравнСниС, доступ ΠΊ памяти ΠΈ Ρ‚.Π΄. Но Π² ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ ΠΎΡ‚ Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΡ… ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€ΠΎΠ², всС эти простыС ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ Π·Π°Π½ΠΈΠΌΠ°ΡŽΡ‚ ΠΎΠ΄Π½Ρƒ Π΅Π΄ΠΈΠ½ΠΈΡ†Ρƒ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° эквивалСнтно количСству выполняСмых ΠΈΠΌ ΠΏΡ€ΠΈΠΌΠΈΡ‚ΠΈΠ²Π½Ρ‹Ρ… ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ. Π’Π°ΠΊΠΆΠ΅ прСдполагаСтся, Ρ‡Ρ‚ΠΎ машина ΠΈΠΌΠ΅Π΅Ρ‚ Π±Π΅ΡΠΊΠΎΠ½Π΅Ρ‡Π½ΡƒΡŽ ΠΏΠ°ΠΌΡΡ‚ΡŒ, Π° Ρ†Π΅Π»Ρ‹Π΅ числа ΠΈΠΌΠ΅ΡŽΡ‚ фиксированный Ρ€Π°Π·ΠΌΠ΅Ρ€. ВрСмя, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ΅ для Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½ΠΈΡ Ρ†ΠΈΠΊΠ»Π°, ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ количСству ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΉ ΡƒΠΌΠ½ΠΎΠΆΠ΅Π½Π½ΠΎΠΌΡƒ Π½Π° ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ.

АсимптотичСский Π°Π½Π°Π»ΠΈΠ·

Когда прСдставлСны Π΄Π²Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, Ρ€Π΅ΡˆΠ°ΡŽΡ‰ΠΈΠ΅ ΠΎΠ΄Π½Ρƒ ΠΈ Ρ‚Ρƒ ΠΆΠ΅ Π·Π°Π΄Π°Ρ‡Ρƒ, ΠΈ Π½Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ, ΠΊΠ°ΠΊΠΎΠΉ ΠΈΠ· Π½ΠΈΡ… быстрСС, ΠΎΠ΄ΠΈΠ½ ΠΈΠ· Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… способов – Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Ρ‚ΡŒ эти Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹, Π·Π°ΠΏΡƒΡΡ‚ΠΈΡ‚ΡŒ ΠΈΡ… с Ρ€Π°Π·Π½Ρ‹ΠΌΠΈ Π²Ρ…ΠΎΠ΄Π½Ρ‹ΠΌΠΈ Π΄Π°Π½Π½Ρ‹ΠΌΠΈ ΠΈ ΠΈΠ·ΠΌΠ΅Ρ€ΠΈΡ‚ΡŒ врСмя выполнСния. Но это Π½Π΅ Π»ΡƒΡ‡ΡˆΠ΅Π΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΎΠ΄ΠΈΠ½ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ быстрСС ΠΏΡ€ΠΈ нСбольшом количСствС Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… ΠΈ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅ ΠΏΡ€ΠΈ большСм. Π§Ρ‚ΠΎΠ±Ρ‹ Ρ‚ΠΎΡ‡Π½ΠΎ ΠΏΡ€ΠΎΠ°Π½Π°Π»ΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ, программисты ΡΠΏΡ€Π°ΡˆΠΈΠ²Π°ΡŽΡ‚, ΠΊΠ°ΠΊ быстро увСличиваСтся врСмя выполнСния ΠΏΡ€ΠΈ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠΈ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. НапримСр, ΠΊΠΎΠ³Π΄Π° Ρ€Π°Π·ΠΌΠ΅Ρ€ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… удваиваСтся, увСличиваСтся Π»ΠΈ врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ? Или ΠΎΠ½ΠΎ увСличиваСтся Π² Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ Ρ€Π°Π·Π°, Π° ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ, Π΄Π°ΠΆΠ΅ ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎ?

Π’Π΅ ΠΆΠ΅ вопросы ΠΌΠΎΠΆΠ½ΠΎ Π·Π°Π΄Π°Ρ‚ΡŒ ΠΈ ΠΎ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π² Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… условиях. Для Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Ρ€Π°Π·ΠΌΠ΅Ρ€ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… Π½Π΅ являСтся СдинствСнным Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΎΠΌ, Π½ΠΎ особСнности Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… Ρ‚Π°ΠΊΠΆΠ΅ Π²Π»ΠΈΡΡŽΡ‚ Π½Π° врСмя выполнСния. Π’ качСствС ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° ΠΌΠΎΠΆΠ½ΠΎ привСсти Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΉ поиск. Π­Ρ‚ΠΎ простой Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ для нахоТдСния элСмСнта Π² спискС. Он ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ провСряСт ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ элСмСнт списка Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π½Π΅ ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠΈΡ‚ совпадСниС ΠΈΠ»ΠΈ ΠΏΠΎΠΊΠ° Π½Π΅ просмотрит вСсь список. ΠžΡ‡Π΅Π²ΠΈΠ΄Π½ΠΎ, Ρ‡Ρ‚ΠΎ врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ этого Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ‚ Ρ€Π΅Π·ΠΊΠΎ ΠΎΡ‚Π»ΠΈΡ‡Π°Ρ‚ΡŒΡΡ для списков с ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΌ Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠΌ n. Π’ Π»ΡƒΡ‡ΡˆΠ΅ΠΌ случаС, Ссли искомый элСмСнт являСтся ΠΏΠ΅Ρ€Π²Ρ‹ΠΌ Π² спискС, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ трСбуСтся Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½ΠΎ сравнСниС. Π‘ Π΄Ρ€ΡƒΠ³ΠΎΠΉ стороны, Ссли Π² спискС отсутствуСт Π½ΡƒΠΆΠ½Ρ‹ΠΉ элСмСнт ΠΈΠ»ΠΈ ΠΎΠ½ оказался послСдним, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ Ρ€ΠΎΠ²Π½ΠΎ n сравнСний. Π’ Ρ†Π΅Π»ΠΎΠΌ, ΠΏΡ€ΠΈ Π°Π½Π°Π»ΠΈΠ·Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΡ… Π΄Π²ΡƒΡ… ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΎΠ²: Π»ΠΈΠ±ΠΎ ΠΌΠΎΠΆΠ½ΠΎ ΡΡ‡ΠΈΡ‚Π°Ρ‚ΡŒ Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ Π΄Π°Π½Π½Ρ‹Π΅ случайными ΠΈ Π°Π½Π°Π»ΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΡΡ€Π΅Π΄Π½ΡŽΡŽ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ, Π»ΠΈΠ±ΠΎ ΠΌΡ‹ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ΄ΠΎΠ±Ρ€Π°Ρ‚ΡŒ Ρ…ΡƒΠ΄ΡˆΠΈΠ΅ Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ Π΄Π°Π½Π½Ρ‹Π΅ ΠΈ ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚ΡŒ Π½Π°ΠΈΡ…ΡƒΠ΄ΡˆΡƒΡŽ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ. Π’ этой сСрии статСй ΠΌΡ‹ Π±ΡƒΠ΄Π΅ΠΌ ΠΏΡ€ΠΈΠ΄Π΅Ρ€ΠΆΠΈΠ²Π°Ρ‚ΡŒΡΡ Π°Π½Π°Π»ΠΈΠ·Π° Π½Π°ΠΈΡ…ΡƒΠ΄ΡˆΠ΅Π³ΠΎ случая, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ это Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΠ΅Ρ‚, Ρ‡Ρ‚ΠΎ для любого ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… Ρ€Π°Π·ΠΌΠ΅Ρ€Π° n врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π½Π΅ прСвысит ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½Π½ΠΎΠ³ΠΎ ΠΏΡ€Π΅Π΄Π΅Π»Π°. ΠšΡ€ΠΎΠΌΠ΅ Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ ΠΌΡ‹ опрСдСляСм "срСдниС" Π΄Π°Π½Π½Ρ‹Π΅, ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΠΎΠ²Π»ΠΈΡΡ‚ΡŒ Π½Π° Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Π°Π½Π°Π»ΠΈΠ·Π°.

«O» большоС

АсимптотичСский Π°Π½Π°Π»ΠΈΠ· позволяСт ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ алгоритмас Ρ‚ΠΎΡ‡ΠΊΠΈ зрСния Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ врСмя (ΠΈΠ»ΠΈ ΠΏΠ°ΠΌΡΡ‚ΡŒ), Π·Π°Π½ΠΈΠΌΠ°Π΅ΠΌΠΎΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ,увСличиваСтся с возрастаниСм количСства Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Π’ асимптотичСскихобозначСниях ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ функция для описания ΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡ ΠΌΠ΅ΠΆΠ΄ΡƒΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΈ Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠΌ Π·Π°Π΄Π°Ρ‡ΠΈ, ΠΊΠΎΠ³Π΄Π° ΠΎΠ½Π° становится большой.Π’ связи с ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΠΌ Ρ…Π°Ρ€Π°ΠΊΡ‚Π΅Ρ€ΠΎΠΌ ΡΡ‚Π°Ρ‚ΡŒΠΈ ΠΌΡ‹ ограничимся Ρ‚ΠΎΠ»ΡŒΠΊΠΎ большим "O" ΠΈ Π½Π΅Π·Π°Ρ‚Ρ€ΠΎΠ½Π΅ΠΌ ΠΌΠ½ΠΎΠ³ΠΈΠ΅ Π½ΡŽΠ°Π½ΡΡ‹ асимптотичСского Π°Π½Π°Π»ΠΈΠ·Π°. Говоря простым языком, Π΅ΡΠ»ΠΈΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Ρ€Π°Π²Π½Π° O(n2), это ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ увСличиваСтся ΠΊΠ°ΠΊΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… n. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, Ссли Ρ€Π°Π·ΠΌΠ΅Ρ€ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…Ρ€Π°Π²Π΅Π½ n, врСмя выполнСния ΠΏΡ€ΠΈΠ±Π»ΠΈΠ·ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ составляСт n2. Π”Ρ€ΡƒΠ³ΠΈΠΌΠΈ словами, Ссливы ΡƒΠ΄Π²ΠΎΠΈΡ‚Π΅ Ρ€Π°Π·ΠΌΠ΅Ρ€ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…, Ρ‚ΠΎ врСмя выполнСния возрастСт ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π½ΠΎ Π²Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ Ρ€Π°Π·Π°. НиТС ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Ρ‹ основныС ΠΏΡ€Π°Π²ΠΈΠ»Π° для вычислСния большого "O"Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°:
1. Если Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ f(n) ΠΏΡ€ΠΈΠΌΠΈΡ‚ΠΈΠ²Π½Ρ‹Ρ… ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ, Ρ‚ΠΎ ΠΎΠ½ ΠΈΠΌΠ΅Π΅Ρ‚ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ O(f(n)).2. Если Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ выполняСт ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ, которая Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ‚ f(n)g(n) Ρ€Π°Π·, Ρ‚ΠΎΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° составляСт O(f(n)βˆ—g(n)).3. Если Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΈΠΌΠ΅Π΅Ρ‚ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ cO(f(n)), Π³Π΄Π΅ c - константа, Ρ‚ΠΎ Π΅Π³ΠΎΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΌΠΎΠΆΠ½ΠΎ ΡƒΠΏΡ€ΠΎΡΡ‚ΠΈΡ‚ΡŒ Π΄ΠΎ O(f(n)). Π˜Π½Π°Ρ‡Π΅ говоря, константы ΠΌΠΎΠΆΠ½ΠΎΠΎΠΏΡƒΡΠΊΠ°Ρ‚ΡŒ.4. Если Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ выполняСт ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ, которая Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ‚ O(f(n)) ΡˆΠ°Π³ΠΎΠ², Π°Π·Π°Ρ‚Π΅ΠΌ выполняСт Π΄Ρ€ΡƒΠ³ΡƒΡŽ ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Ρƒ, которая Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ‚ O(g(n)) ΡˆΠ°Π³ΠΎΠ², тообщая ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Ρ€Π°Π²Π½Π° O(f(n)+g(n)).5. Если Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΈΠΌΠ΅Π΅Ρ‚ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ O(f(n)+g(n)) ΠΏΡ€ΠΈ этом g(n)<f(n), Π΄Π»ΡΠ±ΠΎΠ»ΡŒΡˆΠΈΡ… n, Ρ‚ΠΎ Π΅Π³ΠΎ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΌΠΎΠΆΠ½ΠΎ ΡƒΠΏΡ€ΠΎΡΡ‚ΠΈΡ‚ΡŒ Π΄ΠΎ O(f(n)).

Π­Ρ‚ΠΈ ΠΏΡ€Π°Π²ΠΈΠ»Π° просты Π² ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠΈ, нСсмотря Π½Π° ΠΊΠ°ΠΆΡƒΡ‰ΡƒΡŽΡΡ Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ. ΠœΡ‹ ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠΌ ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΠΈΠ· этих ΠΏΡ€Π°Π²ΠΈΠ» Π½Π° ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΠ±Π»Π΅Π³Ρ‡ΠΈΡ‚ΡŒ ΠΈΡ… усвоСниС.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ ΠΏΡ€Π°Π²ΠΈΠ»Π° 1: ВзглянитС Π½Π° Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΡŽ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ вычисляСт сумму всСх элСмСнтов Π² массивС, Π½Π° языкС C++.

sum.cpp
        int sum(int* array, int n)
{
    int sum = 0;
    for(int i=0;i<n;++i)
    {
        sum+=array[i];
    }
    return sum;
}

    
Данная ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° выполняСт ΠΎΠ΄Π½ΠΎ присваиваниС Π΄ΠΎ Π½Π°Ρ‡Π°Π»Π° Ρ†ΠΈΠΊΠ»Π°, n ΠΏΡ€ΠΈΡΠ²Π°ΠΈΠ²Π°Π½ΠΈΠΉΠ²Π½ΡƒΡ‚Ρ€ΠΈ Ρ†ΠΈΠΊΠ»Π° ΠΈ Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ сумму послС. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, для выполнСния трСбуСтсяn+2 ΠΏΡ€ΠΎΡΡ‚Ρ‹Ρ… ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ, согласно ΠΏΡ€Π°Π²ΠΈΠ»Ρƒ 1, Π΅Π΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Ρ€Π°Π²Π½Π° O(n+2).

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ ΠΏΡ€Π°Π²ΠΈΠ» 2 ΠΈ 3: ΠŸΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½Π°Ρ Π½ΠΈΠΆΠ΅ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° складываСт Π΄Π²Π΅ ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚Π½Ρ‹Π΅ ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹.

matrixAddition.cpp
        void matrixAddition(int** m1, int** m2, int** dest, int n)
{
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            dest[i][j]=m1[i][j]+m2[i][j];
        }
    }
}

    
Π­Ρ‚ΠΎΡ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ состоит ΠΈΠ· Π΄Π²ΡƒΡ… Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… Ρ†ΠΈΠΊΠ»ΠΎΠ². Π’Π½ΡƒΡ‚Ρ€Π΅Π½Π½ΠΈΠΉ Ρ†ΠΈΠΊΠ» выполняСт nΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΉ, ΠΏΡ€ΠΈΡ‡Π΅ΠΌ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ шаг состоит ΠΈΠ· Π΄Π²ΡƒΡ… простых дСйствий: слоТСния иприсваивания. ΠŸΡ€ΠΈΠΌΠ΅Π½ΡΡ ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ 2, ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ Π²Ρ‹Π²ΠΎΠ΄, Ρ‡Ρ‚ΠΎ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΠ²Π½ΡƒΡ‚Ρ€Π΅Π½Π½Π΅Π³ΠΎ Ρ†ΠΈΠΊΠ»Π° Ρ€Π°Π²Π½Π° O(2n). Π’Π½Π΅ΡˆΠ½ΠΈΠΉ Ρ†ΠΈΠΊΠ» Ρ‚Π°ΠΊΠΆΠ΅ Π΄Π΅Π»Π°Π΅Ρ‚ n ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΉ, Π½ΠΎ Π²ΠΌΠ΅ΡΡ‚ΠΎΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Π½ΠΈΡ простых ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ ΠΎΠ½ запускаСт Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½ΠΈΠΉ Ρ†ΠΈΠΊΠ». ΠŸΠΎΠ²Ρ‚ΠΎΡ€Π½ΠΎΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠ² ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ 2, ΠΌΡ‹ Π·Π°ΠΊΠ»ΡŽΡ‡Π°Π΅ΠΌ, Ρ‡Ρ‚ΠΎ внСшний Ρ†ΠΈΠΊΠ» (Π° Π·Π½Π°Ρ‡ΠΈΡ‚ ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ) ΠΈΠΌΠ΅Π΅Ρ‚ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ O(nβˆ—2βˆ—n)=(2n2). Π’Π°ΠΊΠΆΠ΅ ΠΏΠΎ ΠΏΡ€Π°Π²ΠΈΠ»Ρƒ 3 ΠΌΠΎΠΆΠ½ΠΎ ΠΈΠ·Π±Π°Π²ΠΈΡ‚ΡŒΡΡ ΠΎΡ‚ константы,ΠΈ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ O(n2). ΠšΠΎΠ½ΡΡ‚Π°Π½Ρ‚Π½Ρ‹Π΅ ΠΌΠ½ΠΎΠΆΠΈΡ‚Π΅Π»ΠΈ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠΏΡƒΡΡ‚ΠΈΡ‚ΡŒ, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΎΠ½ΠΈ Π½Π΅Π²Π»ΠΈΡΡŽΡ‚ Π½Π° асимптотичСскоС ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°. Однако ΠΎΠ½ΠΈ ΠΈΠΌΠ΅ΡŽΡ‚ Π±ΠΎΠ»ΡŒΡˆΠΎΠ΅ΠΏΡ€Π°ΠΊΡ‚ΠΈΡ‡Π΅ΡΠΊΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ с Ρ‚ΠΎΠΉ ΠΆΠ΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ, Π½ΠΎ Π²Π΄Π²ΠΎΠ΅ быстрСС,всСгда ΠΏΡ€Π΅Π΄ΠΏΠΎΡ‡Ρ‚ΠΈΡ‚Π΅Π»ΡŒΠ½Π΅Π΅.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ ΠΏΡ€Π°Π²ΠΈΠ» 4 ΠΈ 5: ΠžΠ±Ρ€Π°Ρ‚ΠΈΡ‚Π΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π½Π° ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ Π½ΠΈΠΆΠ΅

function.cpp
        void function(int** dest, int n)
{
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            dest[i][j]=1;
        }
    }

    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            for(int k = 0; k < n; ++k)
            {
                dest[i][j]=2;
            }
        }
    }
}
    
Π­Ρ‚Π° ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€Π° выполняСт Π΄Π²Π°ΠΆΠ΄Ρ‹ Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ» с суммарной ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ O(n2),Π° Π·Π°Ρ‚Π΅ΠΌ Ρ‚Ρ€ΠΈΠΆΠ΄Ρ‹ Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ» со ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ O(n3). Π’ соотвСтствии с ΠΏΡ€Π°Π²ΠΈΠ»ΠΎΠΌ 4ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° составляСт O(n3+n2). А ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ n3 Π±ΠΎΠ»ΡŒΡˆΠ΅, Ρ‡Π΅ΠΌ n2, ΠΌΡ‹ΠΌΠΎΠΆΠ΅ΠΌ ΡƒΠΌΠ΅Π½ΡŒΡˆΠΈΡ‚ΡŒ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π΄ΠΎ O(n3), ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠ² ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ 5. Π‘ матСматичСскойточки зрСния, ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π΅Π½ΠΈΠ΅, Ρ‡Ρ‚ΠΎ ΠΎΠ΄Π½Π° функция большС Π΄Ρ€ΡƒΠ³ΠΎΠΉ, Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ‚ смысла. ВалгоритмичСском Π°Π½Π°Π»ΠΈΠ·Π΅ f(n)<g(n) ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ g(n) ΡΡ‚Π°Π½ΠΎΠ²ΠΈΡ‚ΡΡΠ½Π΅Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ ΠΏΠΎ ΡΡ€Π°Π²Π½Π΅Π½ΠΈΡŽ с f(n), ΠΊΠΎΠ³Π΄Π° n ΡΡ‚ановится ΠΎΡ‡Π΅Π½ΡŒ большой. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒΠ³ΠΎΠ²ΠΎΡ€ΡΡ‚, Ρ‡Ρ‚ΠΎ f(n)+g(n) ΠΈ f(n) Π°ΡΠΈΠΌΠΏΡ‚отичСски эквивалСнтны, Π° g(n) ΠΌΠΎΠΆΠ½ΠΎΡƒΠ΄Π°Π»ΡΡ‚ΡŒ. НС обращая внимания Π½Π° мСньшиС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΈΠ·Π±Π΅ΠΆΠ°Ρ‚ΡŒ Π°Π½Π°Π»ΠΈΠ·Π°ΠΌΠ΅Π»ΠΊΠΈΡ… Π·Π°Π΄Π°Ρ‡ ΠΏΠΎ ΠΏΠΎΠ΄Π³ΠΎΡ‚ΠΎΠ²ΠΊΠ΅ ΠΈ очистки ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ ΠΈ ΡΠΎΡΡ€Π΅Π΄ΠΎΡ‚ΠΎΡ‡ΠΈΡ‚ΡŒΡΡ наасимптотичСском ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠΈ ΠΏΡ€ΠΈ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠΈ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Π’Π΅ΠΌ Π½Π΅ ΠΌΠ΅Π½Π΅Π΅,практичСскоС врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΈΠ½ΠΎΠ³Π΄Π° ΠΌΠΎΠΆΠ΅Ρ‚ Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΡ‚Π»ΠΈΡ‡Π°Ρ‚ΡŒΡΡ ΠΎΡ‚ СготСорСтичСского повСдСния. Рассмотрим Π΄Π²Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΈΠΌΠ΅Π΅Ρ‚ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ O(log⁑n), ΠΈ выполняСт log⁑n+1000000000 Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… шагов.Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π²Ρ‚ΠΎΡ€ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° составляСт O(n2), Π° Π½Π° ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ n2+10ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ. НСсмотря Π½Π° Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ асимптотичСская ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°Π΄ΠΎΠ²ΠΎΠ»ΡŒΠ½ΠΎ низкая, ΠΎΠ½ Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒΡΡ Π½Π°ΠΌΠ½ΠΎΠ³ΠΎ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅, Ссли Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ Π΄Π°Π½Π½Ρ‹Π΅Π½Π΅ ΠΎΡ‡Π΅Π½ΡŒ большиС.

Часто Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‰ΠΈΠ΅ΡΡ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния

Π’ этом Ρ€Π°Π·Π΄Π΅Π»Π΅ ΠΌΡ‹ рассмотрим нСсколько Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ распространСнныС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‚ΡΡ ΠΏΡ€ΠΈ Π°Π½Π°Π»ΠΈΠ·Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ². Знакомство с этими функциями даст Π²Π°ΠΌ Ρ…ΠΎΡ€ΠΎΡˆΠ΅Π΅ прСдставлСниС ΠΎΠ± особСнностях Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π²Ρ€Π΅ΠΌΠ΅Π½ выполнСния ΠΈ ΠΏΠΎΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ, являСтся Π»ΠΈ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ вашСго Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΏΡ€ΠΈΠ΅ΠΌΠ»Π΅ΠΌΠΎΠΉ.

O(1) - Если Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ выполняСт ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎΠ΅ количСство ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ Π² нСзависимости ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…, ΠΎΠ½ ΠΈΠΌΠ΅Π΅Ρ‚ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ O(1).O(log⁑n)βˆ’ΠšΠΎΠ³Π΄Π° ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° логарифмичСская, ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° становится лишьнСмного ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅ ΠΏΠΎ ΠΌΠ΅Ρ€Π΅ роста n. ΠŸΡ€ΠΈ ΡƒΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠΈ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… накоэффициСнт основания Π»ΠΎΠ³Π°Ρ€ΠΈΡ„ΠΌΠ° врСмя выполнСния увСличиваСтся Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π½Π° константу.Π§Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎΠ½ΡΡ‚ΡŒ, насколько ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ растСт врСмя выполнСния, ΠΏΠΎΠ΄ΡƒΠΌΠ°ΠΉΡ‚Π΅ ΠΎ Ρ‚ΠΎΠΌ, ΡΠΊΠΎΠ»ΡŒΠΊΠΎΠ±ΠΈΡ‚ трСбуСтся для хранСния n. ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ это количСство Ρ€Π°Π²Π½ΠΎ βŒˆlog2⁑⁑(n+1)βŒ‰, логарифмичСскоС врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ числу Π±ΠΈΡ‚ΠΎΠ², ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Ρ…Π΄Π»Ρ хранСния n. ΠŸΡ€ΠΈ ΡƒΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠΈ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π° Π½Π° Π΄Π²Π° число Π±ΠΈΡ‚ΠΎΠ² увСличиваСтся Π½Π°Π΅Π΄ΠΈΠ½ΠΈΡ†Ρƒ. Аналогично, ΠΏΡ€ΠΈ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠΈ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… Π² Π΄Π²Π° Ρ€Π°Π·Π° врСмяработы увСличиваСтся Π½Π° Π΅Π΄ΠΈΠ½ΠΈΡ†Ρƒ. НапримСр, ΠΊΠΎΠ³Π΄Π° Ρ€Π°Π·ΠΌΠ΅Ρ€ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…Ρ€Π°Π²Π΅Π½ ΠΌΠΈΠ»Π»ΠΈΠ°Ρ€Π΄Ρƒ, врСмя выполнСния Ρ€Π°Π²Π½ΠΎ 30, Π° ΠΊΠΎΠ³Π΄Π° Ρ€Π°Π·ΠΌΠ΅Ρ€ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… Ρ€Π°Π²Π΅Π½Π΄Π²ΡƒΠΌ ΠΌΠΈΠ»Π»ΠΈΠ°Ρ€Π΄Π°ΠΌ, ΠΎΠ½Π° Ρ€Π°Π²Π½ΠΎ 31. ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ logb⁑⁑n=loga⁑⁑nloga⁑⁑b, Π³Π΄Π΅ 1logb⁑⁑a -константа, основаниС Π»ΠΎΠ³Π°Ρ€ΠΈΡ„ΠΌΠ° Π² Π½ΠΎΡ‚Π°Ρ†ΠΈΠΈ большого «О» ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ опускаСтся.ЛогарифмичСскоС врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Ρ…Π°Ρ€Π°ΠΊΡ‚Π΅Ρ€Π½ΠΎ для ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΡƒΡŽΡ‚Π±ΠΎΠ»ΡŒΡˆΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ Π² ΡΠ΅Ρ€ΠΈΡŽ ΠΌΠ΅Π½ΡŒΡˆΠΈΡ… Π·Π°Π΄Π°Ρ‡, ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ шаг ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… Π΄Π΅Π»ΠΈΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€ Π·Π°Π΄Π°Ρ‡ΠΈΠ½Π° ΠΏΠΎΡΡ‚ΠΎΡΠ½Π½ΡƒΡŽ Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Ρƒ. ΠŸΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, ΠΈΠΌΠ΅ΡŽΡ‰Π΅Π³ΠΎ Ρ‚Π°ΠΊΡƒΡŽ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ,являСтся Π΄Π²ΠΎΠΈΡ‡Π½Ρ‹ΠΉ поиск. Π”Π²ΠΎΠΈΡ‡Π½Ρ‹ΠΉ поиск - это эффСктивный ΠΌΠ΅Ρ‚ΠΎΠ΄ нахоТдСнияэлСмСнта Π² отсортированном спискС. Он Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ ΠΏΡƒΡ‚Π΅ΠΌ сравнСния цСлСвогозначСния с элСмСнтом Π² сСрСдинС. ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ список отсортирован, искомый элСмСнтдолТСн Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ справа, Ссли Ρ†Π΅Π»Π΅Π²ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ большС срСднСго элСмСнта. ЕслизначСниС искомого элСмСнта мСньшС, Ρ‚ΠΎ ΠΎΠ½ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ слСва. Π­Ρ‚ΠΎ Π·Π½Π°Π½ΠΈΠ΅ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ‚ΠΈΡΠΊΠ»ΡŽΡ‡ΠΈΡ‚ΡŒ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Ρƒ искомой области Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ.O(n) - Если врСмя выполнСния ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ являСтся Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΌ, Ρ‚ΠΎ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉΠ²Ρ…ΠΎΠ΄Π½ΠΎΠΉ элСмСнт подвСргаСтся ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ с постоянной ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ. Когда n Ρ€Π°Π²Π½ΠΎΠΌΠΈΠ»Π»ΠΈΠΎΠ½Ρƒ, врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Ρ‚Π°ΠΊΠΆΠ΅ равняСтся ΠΌΠΈΠ»Π»ΠΈΠΎΠ½Ρƒ. Если n удваиваСтся, врСмяработы Ρ‚Π°ΠΊΠΆΠ΅ удваиваСтся. Для Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ всС nисходных Π΄Π°Π½Π½Ρ‹Ρ…, такая ситуация являСтся ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ. НахоТдСниС Π½Π°ΠΈΠ±ΠΎΠ»ΡŒΡˆΠ΅Π³ΠΎΡΠ»Π΅ΠΌΠ΅Π½Ρ‚Π° Π² нСсортированном спискС являСтся ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ Ρ‚Π°ΠΊΠΎΠΉ случая, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ элСмСнт рассматриваСтся ΠΈ сравниваСтся с Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΌ максимумом.O(nlog⁑n) - O(nlog⁑n) Ρ€Π°ΡΡ‚Π΅Ρ‚ быстрСС Ρ‡Π΅ΠΌ линСйная функция, Π½ΠΎ Π½Π΅Π½Π°ΠΌΠ½ΠΎΠ³ΠΎ. Π’Π°ΠΊΠ°ΡΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ Π²ΠΎΠ·Π½ΠΈΠΊΠ°Π΅Ρ‚, ΠΊΠΎΠ³Π΄Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Ρ€Π°Π·Π±ΠΈΠ²Π°Π΅Ρ‚ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡƒ Π½Π° ΠΏΠΎΠ΄Π·Π°Π΄Π°Ρ‡ΠΈ,Ρ€Π΅ΡˆΠ°Π΅Ρ‚ ΠΈΡ… ΠΈ ΠΎΠ±ΡŠΠ΅Π΄ΠΈΠ½ΡΠ΅Ρ‚ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ. Π­Ρ‚ΠΎΡ‚ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ ΠΊ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² называСтся "раздСляй ΠΈ властвуй". O(nlog⁑n) ΡΠ²Π»ΡΠ΅Ρ‚ся ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ для Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировкина основС сравнСния. Π’ дальнСйшСм ΠΌΡ‹ Π±ΠΎΠ»Π΅Π΅ ΠΏΠΎΠ΄Ρ€ΠΎΠ±Π½ΠΎ рассмотрим Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹"раздСляй ΠΈ властвуй" ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ сортировки.
O(n2) - Π’ случаС, ΠΊΠΎΠ³Π΄Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΏΠ΅Ρ€Π΅Π±ΠΈΡ€Π°Π΅Ρ‚ всС Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ Π΄Π°Π½Π½Ρ‹Π΅ ΠΈ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΉΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΏΠ΅Ρ€Π΅Π±ΠΈΡ€Π°Π΅Ρ‚ ΠΈΡ… снова, ΠΎΠ½ ΠΈΠΌΠ΅Π΅Ρ‚ ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΡƒΡŽ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ. Π’ качСствСпримСра рассмотрим ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ, которая Π²Ρ‹Π²ΠΎΠ΄ΠΈΡ‚ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ ΠΏΠ°Ρ€Ρ‹ ΠΈΠ· элСмСнтовмассива:
displayPairs
        void displayPairs(int* array, int n)
{
    int count = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            count++;
            cout<< "Pair #"<<count<<':'<< array[i] <<'-' << array[j] <<endl;
        }
    }
}

    
Π§Ρ‚ΠΎΠ±Ρ‹ ΠΎΡ‚ΠΎΠ±Ρ€Π°Π·ΠΈΡ‚ΡŒ всС ΠΏΠ°Ρ€Ρ‹, ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ элСмСнт массива Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ сопряТСн скаТдым Π΄Ρ€ΡƒΠ³ΠΈΠΌ элСмСнтом. Алгоритмы с ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ ΠΏΡ€Π°ΠΊΡ‚ΠΈΡ‡Π½Ρ‹Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΏΡ€ΠΈ срСдних ΠΈΠ»ΠΈ ΠΌΠ°Π»Ρ‹Ρ… Ρ€Π°Π·ΠΌΠ΅Ρ€Π°Ρ… Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Когда ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΠ°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Ρ€Π°Π²Π½Π° O(nk), Π³Π΄Π΅ k - константа, говорят, Ρ‡Ρ‚ΠΎ ΠΎΠ½ ΠΈΠΌΠ΅Π΅Ρ‚ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅Π²Ρ€Π΅ΠΌΡ выполнСния. Π’ эту ΠΊΠ°Ρ‚Π΅Π³ΠΎΡ€ΠΈΡŽ входят Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹Π΅, ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½Ρ‹Π΅, кубичСскиС ΠΈΠ΄Π°ΠΆΠ΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ O(n100). На Π΄Π΅Π»Π΅, ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡŒΠ½Ρ‹Π΅ Π²Ρ€Π΅ΠΌΠ΅Π½Π° выполнСния высокогопорядка Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‚ΡΡ Ρ€Π΅Π΄ΠΊΠΎ, Π½ΠΎ ΠΎΠ½ΠΈ быстрСС, Ρ‡Π΅ΠΌ ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Π΅ ΠΈΡ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π»ΡŒΠ½Ρ‹Π΅ Π²Ρ€Π΅ΠΌΠ΅Π½Π° выполнСния.
O(2n) - НСсмотря Π½Π° Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ Ρ‚Π°ΠΊΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡŽΡ‚ СстСствСнным ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ ΠΏΡ€ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΈ ΠΌΠ½ΠΎΠ³ΠΈΡ… Π·Π°Π΄Π°Ρ‡ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€Π°, лишь Π½Π΅ΠΌΠ½ΠΎΠ³ΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ с ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹ΠΌ Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΡ€ΠΈΠ³ΠΎΠ΄Π½Ρ‹ для практичСского использования, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΎΠ½ΠΈ растут Ρ‡Ρ€Π΅Π·Π²Ρ‹Ρ‡Π°ΠΉΠ½ΠΎ быстро. ΠŸΡ€ΠΈ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠΈ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π²Ρ…ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½Ρ‚Π° врСмя выполнСния удваиваСтся! Π‘Π°ΠΌΠΎ собой разумССтся, Ρ‡Ρ‚ΠΎ Ρ‚Π°ΠΊΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ бСсполСзны, Ссли Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… Π½Π΅ ΠΎΡ‡Π΅Π½ΡŒ ΠΌΠ°Π». ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹, Ρ€Π΅ΡˆΠ°ΡŽΡ‰ΠΈΠ΅ Π·Π°Π΄Π°Ρ‡Ρƒ ΠΎ Ρ€Π°Π½Ρ†Π΅, ΡΠ²Π»ΡΡŽΡ‚ΡΡ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² с ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠΉ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ. Π’ ΠΏΡ€ΠΎΡΡ‚Π΅ΠΉΡˆΠ΅ΠΉ Π²Π°Ρ€ΠΈΠ°Ρ†ΠΈΠΈ этой Π·Π°Π΄Π°Ρ‡ΠΈ Π΄Π°ΡŽΡ‚ся n ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚ΠΎΠ², ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΡ… вСс ΠΈ Ρ†Π΅Π½Π½ΠΎΡΡ‚ΡŒ ΠΈ Ρ€ΡŽΠΊΠ·Π°ΠΊ, с ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½Π½ΠΎΠΉ Π²ΠΌΠ΅ΡΡ‚ΠΈΠΌΠΎΡΡ‚ΡŒΡŽ. Π’Π°ΡˆΠ° Ρ†Π΅Π»ΡŒ - ΡƒΠ»ΠΎΠΆΠΈΡ‚ΡŒ ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ½ΠΎ большоС число Ρ†Π΅Π½Π½Ρ‹Ρ… Π²Π΅Ρ‰Π΅ΠΉ Π² Ρ€ΡŽΠΊΠ·Π°ΠΊ. ΠšΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚Π° ΠΈΠΌΠ΅Π΅Ρ‚ Π΄Π²Π° состояния: ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚ кладётся Π² Ρ€ΡŽΠΊΠ·Π°ΠΊ, Π»ΠΈΠ±ΠΎ ΠΏΡ€Π΅Π΄ΠΌΠ΅Ρ‚ Π½Π΅ кладётся. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, сущСствуСт 2n ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΉ, ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ Π½ΡƒΠΆΠ½ΠΎ ΡΡ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΆΠ΅ шагов, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠ΅Ρ€Π΅Π±Ρ€Π°Ρ‚ΡŒ ΠΈΡ….
O(n!) - Π€Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π» - самая быстрорастущая ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ встрСчаСтся Π½Π°ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅. Π­Ρ‚Π° функция растСт Π³ΠΎΡ€Π°Π·Π΄ΠΎ быстрСС, Ρ‡Π΅ΠΌ Π΄Π°ΠΆΠ΅ ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½Π°Ρ функция.Для сравнСния, ΠΊΠΎΠ³Π΄Π° Ρ€Π°Π·ΠΌΠ΅Ρ€ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… составляСт всСго 62, Ρ‚ΠΎ количСствовыполняСмых ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ ΠΏΡ€Π΅Π²Ρ‹ΡˆΠ°Π΅Ρ‚ количСство Π°Ρ‚ΠΎΠΌΠΎΠ² Π² ΠΎΠ±ΠΎΠ·Ρ€ΠΈΠΌΠΎΠΉ ВсСлСнной!Π‘ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² с Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π»ΡŒΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ Ρ€Π°ΡΡΡ‚Π°Π²Π»ΡΡŽΡ‚ Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅Π΄Π°Π½Π½Ρ‹Π΅ Π² ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΌ порядкС. Если Π΅ΡΡ‚ΡŒ n связанных Π³ΠΎΡ€ΠΎΠ΄ΠΎΠ², Π·Π°Π΄Π°Ρ‡Π° "ΠŸΡƒΡ‚Π΅ΡˆΠ΅ΡΡ‚Π²ΠΈΠ΅ΠΊΠΎΠΌΠΌΠΈΠ²ΠΎΡΠΆΠ΅Ρ€Π°", просит вас ΠΏΡ€ΠΎΠ»ΠΎΠΆΠΈΡ‚ΡŒ ΠΌΠ΅ΠΆΠ΄Ρƒ Π½ΠΈΠΌΠΈ ΠΊΡ€Π°Ρ‚Ρ‡Π°ΠΉΡˆΠΈΠΉ Π·Π°ΠΌΠΊΠ½ΡƒΡ‚Ρ‹ΠΉ ΠΌΠ°Ρ€ΡˆΡ€ΡƒΡ‚,проходящий Ρ‡Π΅Ρ€Π΅Π· ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ Π³ΠΎΡ€ΠΎΠ΄ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄ΠΈΠ½ Ρ€Π°Π·. Π‘Π°ΠΌΡ‹ΠΉ ΠΎΡ‡Π΅Π²ΠΈΠ΄Π½Ρ‹ΠΉ способ -ΠΏΠ΅Ρ€Π΅Π±Ρ€Π°Ρ‚ΡŒ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹. Если всС Π³ΠΎΡ€ΠΎΠ΄Π° связаны ΠΌΠ΅ΠΆΠ΄Ρƒ собой (Π΄Π²Π°Π³ΠΎΡ€ΠΎΠ΄Π° связаны, Ссли ΠΈΠ· ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΎ Π΄ΠΎΡ€ΠΎΠ³Π° Π² Π΄Ρ€ΡƒΠ³ΠΎΠΉ), Ρ‚ΠΎ Ρƒ вас Π΅ΡΡ‚ΡŒ n Π²Π°Ρ€ΠΈΠ°Π½Ρ‚овдля Π²Ρ‹Π±ΠΎΡ€Π° ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ Π³ΠΎΡ€ΠΎΠ΄Π° Π² ΠΌΠ°Ρ€ΡˆΡ€ΡƒΡ‚Π΅, nβˆ’1 Π΄Π»Ρ Π²Ρ‚ΠΎΡ€ΠΎΠ³ΠΎ, nβˆ’2 Π΄Π»Ρ Ρ‚Ρ€Π΅Ρ‚ΡŒΠ΅Π³ΠΎ ΠΈ Ρ‚Π°ΠΊ Π΄Π°Π»Π΅Π΅.Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΠΎΠ±Ρ‰Π΅Π΅ количСство комбинация Ρ€Π°Π²Π½ΠΎ n!

Визуализация Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ

Визуализация Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния Π²Π°ΠΌ наглядно ΠΏΠΎΠΊΠ°ΠΆΠ΅Ρ‚, ΠΏΠΎΡ‡Π΅ΠΌΡƒ Π²Ρ‹Π±ΠΎΡ€ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° с ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ ΠΈΠΌΠ΅Π΅Ρ‚ Ρ‚Π°ΠΊΠΎΠ΅ большоС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅. Π’ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ Π½ΠΈΠΆΠ΅ ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Ρ‹ нСсколько Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ для Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ, описанных Π² ΠΏΡ€Π΅Π΄Ρ‹Π΄ΡƒΡ‰Π΅ΠΌ Ρ€Π°Π·Π΄Π΅Π»Π΅.

πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

На ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΌ Π½ΠΈΠΆΠ΅ ΠΈΠ·ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠΈ ΠΏΠΎΠΊΠ°Π·Π°Π½Ρ‹ Π³Ρ€Π°Ρ„ΠΈΠΊΠΈ распространСнных Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния.

πŸ‘¨β€πŸŽ“οΈ Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° C++ для Π½ΠΎΠ²ΠΈΡ‡ΠΊΠΎΠ². Π§Π°ΡΡ‚ΡŒ 1: ΠžΡΠ½ΠΎΠ²Ρ‹ Π°Π½Π°Π»ΠΈΠ·Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

Π—Π°ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅

Π§Ρ‚ΠΎΠ±Ρ‹ ΠΈΠ·Π²Π»Π΅Ρ‡ΡŒ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΡƒΡŽ ΠΏΠΎΠ»ΡŒΠ·Ρƒ ΠΈΠ· Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΠΎΠ½ΠΈΠΌΠ°Ρ‚ΡŒ Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ‚ΠΎ, ΠΊΠ°ΠΊ ΠΎΠ½ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚, Π½ΠΎ ΠΈ Π΅Π³ΠΎ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ. Π’ этой Π³Π»Π°Π²Π΅ ΠΌΡ‹ объяснили Π½ΠΎΡ‚Π°Ρ†ΠΈΡŽ Π‘ΠΎΠ»ΡŒΡˆΠΎΠ³ΠΎ О, которая ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ для Π°Π½Π°Π»ΠΈΠ·Π° ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°. Если Π²Π°ΠΌ извСстно, ΠΊΠ°ΠΊ выглядит асимптотичСскоС врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, Π²Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ, насколько измСнится врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΡ€ΠΈ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΈ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π·Π°Π΄Π°Ρ‡ΠΈ.

ΠšΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΈ

 
 

Π’ΠΠšΠΠΠ‘Π˜Π˜

Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ вакансию
Π Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊ C++
Москва, ΠΏΠΎ ΠΈΡ‚ΠΎΠ³Π°ΠΌ собСсСдования

Π›Π£Π§Π¨Π˜Π• БВАВЬИ ПО Π’Π•ΠœΠ•

Подпишись

Π½Π° push-увСдомлСния