Найти Π² Π”Π·Π΅Π½Π΅
Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° программиста

πŸ…ΎοΈ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ «О» большоС: объясняСм Π½Π° простых ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π°Ρ…

РасскаТСм просто ΠΈ понятно, ΠΊΠ°ΠΊ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ ΠΈ ΠΏΡ€ΠΎΡΡ‚Ρ€Π°Π½ΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² β€” ΠΈ Π·Π°Ρ‡Π΅ΠΌ Π½ΡƒΠΆΠ½ΠΎ это Π΄Π΅Π»Π°Ρ‚ΡŒ. Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ «О» большоС «О» большоС (Big O notation) β€” это матСматичСская нотация, которая позволяСт ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ, ΠΊΠ°ΠΊ измСняСтся врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΈΠ»ΠΈ объСм ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠΉ памяти Π² зависимости ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Π•ΡΡ‚ΡŒ Π΅Ρ‰Π΅ Β«ΠΎΒ» ΠΌΠ°Π»ΠΎΠ΅ β€” эта нотация Π΄Π°Π΅Ρ‚ Π±ΠΎΠ»Π΅Π΅ ΡΡ‚Ρ€ΠΎΠ³ΡƒΡŽ Π²Π΅Ρ€Ρ…Π½ΡŽΡŽ Π³Ρ€Π°Π½ΠΈΡ†Ρƒ для слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, Π½ΠΎ часто Π΅Π΅ Ρ‚Ρ€ΡƒΠ΄Π½Π΅Π΅ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ, Ρ‡Π΅ΠΌ «О» большоС. На ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅ «О» большоС ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ Ρ‡Π°Ρ‰Π΅, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ эта концСпция ΠΏΡ€ΠΎΡ‰Π΅ для Π°Π½Π°Π»ΠΈΠ·Π° ΠΈ Π΄Π°Π΅Ρ‚ достаточно Ρ…ΠΎΡ€ΠΎΡˆΡƒΡŽ ΠΎΡ†Π΅Π½ΠΊΡƒ слоТности Π² Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²Π΅ случаСв. Π—Π°Ρ‡Π΅ΠΌ Π½ΡƒΠΆΠ½ΠΎ «О» большоС ПониманиС этой Π½ΠΎΡ‚Π°Ρ†ΠΈΠΈ позволяСт: Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²: врСмСнная ΠΈ пространствСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠžΠ±Ρ‹Ρ‡Π½ΠΎ ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² оцСниваСтся ΠΏΠΎ Π΄Π²ΡƒΠΌ критСриям: Как «О» большоС описываСт ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π˜Ρ‚Π°ΠΊ, «О» большоС β€” это способ ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ, ΠΊΠ°ΠΊ врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΈΠ»ΠΈ Ρ‚Ρ€Π΅Π±ΡƒΠ΅ΠΌΡ‹ΠΉ объСм памяти растут с ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠ΅ΠΌ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…
ОглавлСниС

РасскаТСм просто ΠΈ понятно, ΠΊΠ°ΠΊ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ ΠΈ ΠΏΡ€ΠΎΡΡ‚Ρ€Π°Π½ΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² β€” ΠΈ Π·Π°Ρ‡Π΅ΠΌ Π½ΡƒΠΆΠ½ΠΎ это Π΄Π΅Π»Π°Ρ‚ΡŒ.

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ «О» большоС

«О» большоС (Big O notation) β€” это матСматичСская нотация, которая позволяСт ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ, ΠΊΠ°ΠΊ измСняСтся врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΈΠ»ΠΈ объСм ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠΉ памяти Π² зависимости ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Π•ΡΡ‚ΡŒ Π΅Ρ‰Π΅ Β«ΠΎΒ» ΠΌΠ°Π»ΠΎΠ΅ β€” эта нотация Π΄Π°Π΅Ρ‚ Π±ΠΎΠ»Π΅Π΅ ΡΡ‚Ρ€ΠΎΠ³ΡƒΡŽ Π²Π΅Ρ€Ρ…Π½ΡŽΡŽ Π³Ρ€Π°Π½ΠΈΡ†Ρƒ для слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, Π½ΠΎ часто Π΅Π΅ Ρ‚Ρ€ΡƒΠ΄Π½Π΅Π΅ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ, Ρ‡Π΅ΠΌ «О» большоС. На ΠΏΡ€Π°ΠΊΡ‚ΠΈΠΊΠ΅ «О» большоС ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ Ρ‡Π°Ρ‰Π΅, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ эта концСпция ΠΏΡ€ΠΎΡ‰Π΅ для Π°Π½Π°Π»ΠΈΠ·Π° ΠΈ Π΄Π°Π΅Ρ‚ достаточно Ρ…ΠΎΡ€ΠΎΡˆΡƒΡŽ ΠΎΡ†Π΅Π½ΠΊΡƒ слоТности Π² Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²Π΅ случаСв.

Π—Π°Ρ‡Π΅ΠΌ Π½ΡƒΠΆΠ½ΠΎ «О» большоС

ПониманиС этой Π½ΠΎΡ‚Π°Ρ†ΠΈΠΈ позволяСт:

  • Π‘Ρ€Π°Π²Π½ΠΈΠ²Π°Ρ‚ΡŒ ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΈ Ρ‚ΠΎΠΉ ΠΆΠ΅ Π·Π°Π΄Π°Ρ‡ΠΈ.
  • ΠŸΡ€ΠΎΠ³Π½ΠΎΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΏΡ€ΠΈ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠΈ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ….
  • ΠžΠΏΡ‚ΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΊΠΎΠ΄ ΠΏΡƒΡ‚Π΅ΠΌ ΠΈΠ΄Π΅Π½Ρ‚ΠΈΡ„ΠΈΠΊΠ°Ρ†ΠΈΠΈ ΠΈ ΡƒΠ»ΡƒΡ‡ΡˆΠ΅Π½ΠΈΡ слоТных Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ².
  • Π’Ρ‹Π±ΠΈΡ€Π°Ρ‚ΡŒ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ структуры Π΄Π°Π½Π½Ρ‹Ρ… ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΏΡ€ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΈ рСсурсоСмких Π·Π°Π΄Π°Ρ‡.

Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²: врСмСнная ΠΈ пространствСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

ΠžΠ±Ρ‹Ρ‡Π½ΠΎ ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² оцСниваСтся ΠΏΠΎ Π΄Π²ΡƒΠΌ критСриям:

  • ВрСмя выполнСния. ВрСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ β€” это количСство ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ. Она ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚, ΠΊΠ°ΠΊ растСт врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΏΡ€ΠΈ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠΈ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ….
  • ОбъСм ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠΉ памяти. ΠŸΡ€ΠΎΡΡ‚Ρ€Π°Π½ΡΡ‚Π²Π΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° измСряСт объСм памяти, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΎΠ½ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ Π² зависимости ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. На ΠΏΡ€ΠΎΡΡ‚Ρ€Π°Π½ΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π²Π»ΠΈΡΡŽΡ‚ нСсколько Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΎΠ², Π²ΠΊΠ»ΡŽΡ‡Π°Ρ количСство ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…, Ρ‚ΠΈΠΏ ΠΈ Ρ€Π°Π·ΠΌΠ΅Ρ€ структуры Π΄Π°Π½Π½Ρ‹Ρ…, Π²Ρ‹Π·ΠΎΠ²Ρ‹ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ΠΈ способ выдСлСния памяти.

Как «О» большоС описываСт ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

Π˜Ρ‚Π°ΠΊ, «О» большоС β€” это способ ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ, ΠΊΠ°ΠΊ врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΈΠ»ΠΈ Ρ‚Ρ€Π΅Π±ΡƒΠ΅ΠΌΡ‹ΠΉ объСм памяти растут с ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠ΅ΠΌ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ….

ΠŸΡ€ΠΈΠΌΠ΅Ρ€: ΠΏΡ€Π΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ, Ρ‡Ρ‚ΠΎ стоматолог Ρ‚Ρ€Π°Ρ‚ΠΈΡ‚ 30 ΠΌΠΈΠ½ΡƒΡ‚ Π½Π° ΠΏΡ€ΠΈΠ΅ΠΌ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΏΠ°Ρ†ΠΈΠ΅Π½Ρ‚Π°. По ΠΌΠ΅Ρ€Π΅ увСличСния ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ ΠΏΠ°Ρ†ΠΈΠ΅Π½Ρ‚ΠΎΠ², врСмя, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ΅ для ΠΏΡ€ΠΈΠ΅ΠΌΠ° всСх ΠΏΠ°Ρ†ΠΈΠ΅Π½Ρ‚ΠΎΠ², Π±ΡƒΠ΄Π΅Ρ‚ расти Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ количСству ΠΏΠ°Ρ†ΠΈΠ΅Π½Ρ‚ΠΎΠ² Π² ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ.

Учитывая это, ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΎΡ…Π°Ρ€Π°ΠΊΡ‚Π΅Ρ€ΠΈΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ стоматолага ΠΊΠ°ΠΊ Π»ΠΈΠ½Π΅ΠΉΠ½ΡƒΡŽ. Π’ Π½ΠΎΡ‚Π°Ρ†ΠΈΠΈ большого «О» эта ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ выглядит ΠΊΠ°ΠΊ O(n), Π³Π΄Π΅ n Ρ€Π°Π²Π½ΠΎ количСству ΠΏΠ°Ρ†ΠΈΠ΅Π½Ρ‚ΠΎΠ², Π° врСмя, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ΅ стоматологу для Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½ΠΈΡ Ρ€Π°Π±ΠΎΡ‚Ρ‹, растСт Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ ΠΈΠ»ΠΈ ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ количСству ΠΏΠ°Ρ†ΠΈΠ΅Π½Ρ‚ΠΎΠ²:

Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ стоматолога ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠΏΠΈΡΠ°Ρ‚ΡŒ этой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠ΅ΠΉ:

Π—Π΄Π΅ΡΡŒ функция calculateTime слуТит простым ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ для ΠΈΠ»Π»ΡŽΡΡ‚Ρ€Π°Ρ†ΠΈΠΈ ΠΊΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΠΈ большого «О» ΠΈ ΠΏΠΎΡ‚ΠΎΠΌΡƒ Π½Π΅ выполняСт вычислСния, умноТая ΠΏΠ°Ρ†ΠΈΠ΅Π½Ρ‚ΠΎΠ² Π½Π° Π·Π°Ρ‚Ρ€Π°Ρ‡Π΅Π½Π½ΠΎΠ΅ Π½Π° Π½ΠΈΡ… врСмя. ВрСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ этой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ O(n), Π° ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π²Ρ‹Π²ΠΎΠ΄Π° Π² консоль O(1):

РазбСрСмся, ΠΊΠ°ΠΊ ΠΈΠΌΠ΅Π½Π½ΠΎ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ любого Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°.

***

-2

ΠšΡƒΡ€Ρ «Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…Β»

ΠšΡƒΡ€Ρ «Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…Β» для Ρ‚Π΅Ρ…, ΠΊΡ‚ΠΎ Ρ…ΠΎΡ‡Π΅Ρ‚ Π½Π°ΡƒΡ‡ΠΈΡ‚ΡŒΡΡ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ с Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌΠΈ, ΠΏΠΎΠ΄Π³ΠΎΡ‚ΠΎΠ²ΠΈΡ‚ΡŒΡΡ ΠΊ собСсСдованию Π² Ρ‚Π΅Ρ…Π½ΠΎΠ»ΠΎΠ³ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ компанию ΠΈΠ»ΠΈ ΡƒΡ‡Π°ΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ Π² слоТных ΠΏΡ€ΠΎΠ΅ΠΊΡ‚Π°Ρ….

ПослС изучСния Π²Ρ‹:

  • Π£Π·Π½Π°Π΅Ρ‚Π΅ ΠΎ популярных Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°Ρ… ΠΈ структурах Π΄Π°Π½Π½Ρ‹Ρ…
  • ΠŸΠΎΠ»ΡƒΡ‡ΠΈΡ‚Π΅ практичСский ΠΎΠΏΡ‹Ρ‚ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ слоТных алгоритмичСских Π·Π°Π΄Π°Ρ‡
  • Π‘ΠΌΠΎΠΆΠ΅Ρ‚Π΅ Π»Π΅Π³ΠΊΠΎ ΠΏΡ€ΠΎΠΉΡ‚ΠΈ тСхничСскоС собСсСдованиС

Π”ΠΎ 5 мая 2024 Π²ΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ Π½Π° курс дСйствуСт скидка -40%.

ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° обучСния

  • Π’Π²Π΅Π΄Π΅Π½ΠΈΠ΅. ΠŸΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²
  • Π Π°Π±ΠΎΡ‚Π° с числами
  • ΠœΠ°ΡΡΠΈΠ²Ρ‹
  • Бписки. Π‘Ρ‚Π΅ΠΊ, ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ, Π΄Π΅ΠΊ
  • ΠžΡ‡Π΅Ρ€Π΅Π΄ΡŒ с ΠΏΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ΠΎΠΌ
  • ΠžΡΠ½ΠΎΠ²Ρ‹ сортировки
  • ΠŸΠΎΡ€ΡΠ΄ΠΊΠΎΠ²Ρ‹Π΅ статистики
  • Π”Π΅Ρ€Π΅Π²ΡŒΡ
  • Π₯Сш-Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹
  • Π–Π°Π΄Π½Ρ‹Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹. ДинамичСскоС ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅
  • Π“Ρ€Π°Ρ„Ρ‹ ΠΈ рСкурсия
  • Π‘Ρ‚Ρ€ΠΎΠΊΠΈ
  • ΠšΡ€ΠΈΠΏΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΡ
  • Π”Π»ΠΈΠ½Π½Ρ‹Π΅ числа. Π˜Ρ‚ΠΎΠ³ΠΈ

🧠 Π˜Π½Ρ‚Π΅Ρ€Π΅ΡΠ½ΠΎ, Ρ…ΠΎΡ‡Ρƒ ΠΏΠΎΠΏΡ€ΠΎΠ±ΠΎΠ²Π°Ρ‚ΡŒ

(function () { let link = document .getElementById ("826a8b05-d54b-48e8-9511-9b53d4df1896-https://proglib.io/w/53b479ff-28"); if (! link) return; let href = link .getAttribute ("href"); if (! href) return; let prefix = link .dataset .prefix; let action = link .dataset .action; link .addEventListener ("click", function (e) { let data = new FormData (); data .append ("url", href); apiFetch (action, { method: "POST", body: data }) .then (function (res) {}) .catch (function (err) { console .error (err); }); }) })();

ΠžΡΠ½ΠΎΠ²Π½Ρ‹Π΅ ΠΏΡ€Π°Π²ΠΈΠ»Π° вычислСния большого «О»

Π’Ρ€ΠΈ Π³Π»Π°Π²Π½Ρ‹Ρ… ΠΏΡ€Π°Π²ΠΈΠ»Π° вычислСния большого «О» Π²ΠΊΠ»ΡŽΡ‡Π°ΡŽΡ‚:

  • ΠžΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Ρ…ΡƒΠ΄ΡˆΠ΅Π³ΠΎ случая.
  • Π˜ΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ постоянных Π²Π΅Π»ΠΈΡ‡ΠΈΠ½.
  • Π˜Π³Π½ΠΎΡ€ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ всСх процСссов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ быстрСС (ΠΈΠ»ΠΈ Π·Π°Ρ‚Ρ€Π°Ρ‡ΠΈΠ²Π°ΡŽΡ‚ мСньшС памяти), Ρ‡Π΅ΠΌ самая мСдлСнная ΠΈ тяТСлая Ρ‡Π°ΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°.

Рассмотрим всС эти ΠΏΡ€Π°Π²ΠΈΠ»Π° ΠΏΠΎΠ΄Ρ€ΠΎΠ±Π½Π΅Π΅.

Π₯ΡƒΠ΄ΡˆΠΈΠΉ случай

ΠŸΡ€ΠΈ Π°Π½Π°Π»ΠΈΠ·Π΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π²Ρ‹Π΄Π΅Π»ΡΡŽΡ‚ Ρ‚Ρ€ΠΈ случая β€” Π»ΡƒΡ‡ΡˆΠΈΠΉ, срСдний ΠΈ Ρ…ΡƒΠ΄ΡˆΠΈΠΉ:

  • Π›ΡƒΡ‡ΡˆΠΈΠΉ случай ΠΏΠΎΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚, ΠΊΠ°ΠΊ быстро Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ выполняСтся для ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ Π²Ρ…ΠΎΠ΄Π½ΠΎΠ³ΠΎ значСния. Π’ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ с Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠ΅ΠΉ findJoey, которая ΠΈΡ‰Π΅Ρ‚ Joey Π² массивС Π΄Ρ€ΡƒΠ·Π΅ΠΉ, Π»ΡƒΡ‡ΡˆΠΈΠΉ случай происходит, ΠΊΠΎΠ³Π΄Π° Joey находится Π² Π½Π°Ρ‡Π°Π»Π΅ массива. Π’ этом случаС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ выполнится всСго ΠΎΠ΄ΠΈΠ½ Ρ€Π°Π·, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ сразу ΠΆΠ΅ Π½Π°ΠΉΠ΄Π΅Ρ‚ имя ΠΈ ΠΏΡ€Π΅Ρ€Π²Π΅Ρ‚ Ρ†ΠΈΠΊΠ» с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Π° break. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, врСмя выполнСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π² Π»ΡƒΡ‡ΡˆΠ΅ΠΌ случаС составляСт O(1), Ρ‡Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ константноС врСмя выполнСния.
  • Π‘Ρ€Π΅Π΄Π½ΠΈΠΉ случай прСдставляСт собой ΠΏΡ€ΠΎΠ³Π½ΠΎΠ· ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, ΠΊΠΎΠ³Π΄Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ Π΄Π°Π½Π½Ρ‹Π΅ ΡΠ²Π»ΡΡŽΡ‚ΡΡ случайными. Π’ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ findJoey, Π³Π΄Π΅ Joey ΠΌΠΎΠΆΠ΅Ρ‚ Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π² любом мСстС массива, срСдний случай Π±ΡƒΠ΄Π΅Ρ‚ Π·Π°Π²ΠΈΡΠ΅Ρ‚ΡŒ ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ, Π³Π΄Π΅ ΠΈΠΌΠ΅Π½Π½ΠΎ находится Joey. Если Joey находится Π² сСрСдинС массива, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΡ€ΠΎΠΉΡ‚ΠΈ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Ρƒ массива, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π°ΠΉΡ‚ΠΈ Π΅Π³ΠΎ, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Ρ‚ ΠΊ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния O(n/2), Π³Π΄Π΅ n β€” количСство элСмСнтов Π² массивС.
  • Π₯ΡƒΠ΄ΡˆΠΈΠΉ случай ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, ΠΊΠ°ΠΊ Π΄ΠΎΠ»Π³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒΡΡ для прСдоставлСнного Π²Ρ…ΠΎΠ΄Π½ΠΎΠ³ΠΎ значСния. Π’ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ с Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠ΅ΠΉ findJoey, Π³Π΄Π΅ Joey находится Π² ΠΊΠΎΠ½Ρ†Π΅ массива, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ придСтся ΠΏΡ€ΠΎΠΉΡ‚ΠΈ Ρ‡Π΅Ρ€Π΅Π· вСсь массив, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π½Π°ΠΉΡ‚ΠΈ имя. Π’ этом случаС врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° составляСт O(n), Π³Π΄Π΅ n β€” количСство элСмСнтов Π² массивС.

AΠ½Π°Π»ΠΈΠ· Ρ…ΡƒΠ΄ΡˆΠ΅Π³ΠΎ случая позволяСт ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ максимальноС врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°.

Π˜ΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ постоянных Π²Π΅Π»ΠΈΡ‡ΠΈΠ½

ΠŸΡ€ΠΈ расчСтС слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π½Π΅Ρ‚ нСобходимости ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Ρ‚ΡŒ константы. Для ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° снова вСрнСмся ΠΊ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ findJoey, которая ΠΈΡ‰Π΅Ρ‚ Joey Π² массивС Π΄Ρ€ΡƒΠ·Π΅ΠΉ:

ΠŸΡ€ΠΎΡΡƒΠΌΠΌΠΈΡ€ΡƒΠ΅ΠΌ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ выполнСния ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½Ρ‹Ρ… шагов:

ПослС упрощСния ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Ρ€Π°Π²Π½Π° O(n + 3). Однако, ΠΏΡ€ΠΈ расчСтС эффСктивности Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, врСмя выполнСния константных ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ‚ значСния. Π­Ρ‚ΠΎ связано с Ρ‚Π΅ΠΌ, Ρ‡Ρ‚ΠΎ Π΄Π°ΠΆΠ΅ Ссли массив Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΡ‡Π΅Π½ΡŒ большим, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, ΡΠΎΠ΄Π΅Ρ€ΠΆΠ°Ρ‚ΡŒ 2 ΠΌΠΈΠ»Π»ΠΈΠΎΠ½Π° элСмСнтов, эти константныС ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ Π½Π΅ ΠΏΠΎΠ²Π»ΠΈΡΡŽΡ‚ Π½Π° ΠΎΠ±Ρ‰ΡƒΡŽ ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ основной объСм Ρ€Π°Π±ΠΎΡ‚Ρ‹ всС Ρ€Π°Π²Π½ΠΎ Π±ΡƒΠ΄Π΅Ρ‚ Π·Π°ΠΊΠ»ΡŽΡ‡Π°Ρ‚ΡŒΡΡ Π² ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΏΠΎ массиву:

ΠŸΡ€ΠΈΠΌΠ΅Ρ‡Π°Π½ΠΈΠ΅: Ссли функция состоит Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΈΠ· ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ с константами, Ρ‚ΠΎ Π΅Π΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π±ΡƒΠ΄Π΅Ρ‚ константной. НапримСр, функция steps, которая Π²Ρ‹Π²ΠΎΠ΄ΠΈΡ‚ Ρ‚Ρ€ΠΈ увСдомлСния, ΠΈΠΌΠ΅Π΅Ρ‚ Ρ€Π΅Π°Π»ΡŒΠ½ΡƒΡŽ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ O(3). Но ΠΏΠΎ ΠΏΡ€Π°Π²ΠΈΠ»Π°ΠΌ большого «О» ΠΌΡ‹ опрСдСляСм Π΅Π΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΊΠ°ΠΊ O(1), Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΏΡ€Π΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π΅ΠΌ, Ρ‡Ρ‚ΠΎ ΠΎΠ½Π° всСгда Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒΡΡ Π·Π° ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎΠ΅ врСмя:

Π˜Π³Π½ΠΎΡ€ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ всСх Π½Π΅Π΄ΠΎΠΌΠΈΠ½ΠΈΡ€ΡƒΡŽΡ‰ΠΈΡ… процСссов

Π‘ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠ΅ΠΌ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния ΠΈ/ΠΈΠ»ΠΈ объСма потрСблСния памяти ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сниТаСтся. Π’ Π½ΠΎΡ‚Π°Ρ†ΠΈΠΈ большого «О» эта иСрархия выглядит Ρ‚Π°ΠΊ:

   ВозрастаниС слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²
ВозрастаниС слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

ΠŸΡ€ΠΈ ΠΎΡ†Π΅Π½ΠΊΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π΅Π³ΠΎ ΠΈΡ‚ΠΎΠ³ΠΎΠ²ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ являСтся ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ самого ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎΠ³ΠΎ шага. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ ΠΏΡ€ΠΈ ΠΎΡ†Π΅Π½ΠΊΠ΅ этой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΌΡ‹ считаСм Π΅Π΅ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ O(n), ΠΈ ΠΈΠ³Π½ΠΎΡ€ΠΈΡ€ΡƒΠ΅ΠΌ процСссы О(1):

ΠžΡΠ½ΠΎΠ²Π½Ρ‹Π΅ классы слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ²

Классов слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² ΠΌΠ½ΠΎΠ³ΠΎ, здСсь ΠΌΡ‹ рассмотрим Ρ‚ΠΎΠ»ΡŒΠΊΠΎ самыС основныС:

  • O(1) β€” константноС врСмя. Π­Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° остаСтся постоянным, нСзависимо ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€ΠΈΠΌΠ΅Ρ€: доступ ΠΊ элСмСнту массива ΠΏΠΎ индСксу.
  • O(log n) β€” логарифмичСскоС врСмя. ВрСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° увСличиваСтся логарифмичСски ΠΏΠΎ ΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡŽ ΠΊ Ρ€Π°Π·ΠΌΠ΅Ρ€Ρƒ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€ΠΈΠΌΠ΅Ρ€: Π±ΠΈΠ½Π°Ρ€Π½Ρ‹ΠΉ поиск Π² отсортированном массивС.
  • O(n) β€” Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ΅ врСмя. ВрСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° прямо ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€Ρƒ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€ΠΈΠΌΠ΅Ρ€: итСрация ΠΏΠΎ массиву.
  • O(n log n) β€” Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ-логарифмичСскоС врСмя. ВрСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° растСт растСт ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΡŽ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… Π½Π° Π»ΠΎΠ³Π°Ρ€ΠΈΡ„ΠΌ этого Ρ€Π°Π·ΠΌΠ΅Ρ€Π°. ΠŸΡ€ΠΈΠΌΠ΅Ρ€: сортировка слияниСм.
  • O(n^2) β€” ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎΠ΅ врСмя. ВрСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° растСт ΠΊΠ°ΠΊ ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€ΠΈΠΌΠ΅Ρ€: Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ», Π³Π΄Π΅ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ элСмСнт массива сравниваСтся с ΠΊΠ°ΠΆΠ΄Ρ‹ΠΌ Π΄Ρ€ΡƒΠ³ΠΈΠΌ элСмСнтом.
  • O(2^n) β€” ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ врСмя. ВрСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° растСт ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎ ΠΏΠΎ ΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡŽ ΠΊ Ρ€Π°Π·ΠΌΠ΅Ρ€Ρƒ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€ΠΈΠΌΠ΅Ρ€: рСкурсивный Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Ρ€Π΅ΡˆΠ°Π΅Ρ‚ Π·Π°Π΄Π°Ρ‡Ρƒ ΠΏΡƒΡ‚Π΅ΠΌ раздСлСния Π΅Π΅ Π½Π° ΠΏΠΎΠ΄Π·Π°Π΄Π°Ρ‡ΠΈ.
  • O(n!) β€” Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ врСмя. ВрСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° растСт ΠΊΠ°ΠΊ Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π» Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€ΠΈΠΌΠ΅Ρ€: Π·Π°Π΄Π°Ρ‡Π° коммивояТСра, Π³Π΄Π΅ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π½Π°ΠΉΡ‚ΠΈ самый ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΈΠΉ ΠΌΠ°Ρ€ΡˆΡ€ΡƒΡ‚, проходящий Ρ‡Π΅Ρ€Π΅Π· всС Π³ΠΎΡ€ΠΎΠ΄Π°.
  • O(m+n) ΠΈ O(mn). Π’ ΠΏΠ΅Ρ€Π²ΠΎΠΌ случаС врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° растСт Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ ΠΏΠΎ ΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡŽ ΠΊ Ρ€Π°Π·ΠΌΠ΅Ρ€Ρƒ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…, Π° Π²ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΌ случаС врСмя выполнСния Π±ΡƒΠ΄Π΅Ρ‚ ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½Ρ‹ΠΌ. ΠŸΡ€ΠΈΠΌΠ΅Ρ€Ρ‹: Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΉ поиск Π² Π΄Π²ΡƒΠΌΠ΅Ρ€Π½ΠΎΠΌ массивС ΠΈΠΌΠ΅Π΅Ρ‚ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ O(mn), Π° объСдинСниС Π΄Π²ΡƒΡ… отсортированных списков Π² ΠΎΠ±Ρ‰ΠΈΠΉ отсортированный список выполняСтся Π·Π° O(m + n).

ΠŸΡ€Π΅Π΄ΡΡ‚Π°Π²ΠΈΡ‚ΡŒ эффСктивности этих классов ΠΌΠΎΠΆΠ½ΠΎ Ρ‚Π°ΠΊ:

   Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… классов слоТности
Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… классов слоТности

А Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ рассмотрим основныС ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΈ пространствСнной слоТности ΠΏΠΎΠ΄Ρ€ΠΎΠ±Π½Π΅Π΅.

πŸ‘¨β€πŸ’»πŸŽ¨ Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° Ρ„Ρ€ΠΎΠ½Ρ‚Π΅Π½Π΄Π΅Ρ€Π°

Π‘ΠΎΠ»ΡŒΡˆΠ΅ ΠΏΠΎΠ»Π΅Π·Π½Ρ‹Ρ… ΠΌΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»ΠΎΠ² Π²Ρ‹ Π½Π°ΠΉΠ΄Π΅Ρ‚Π΅ Π½Π° нашСм Ρ‚Π΅Π»Π΅Π³Ρ€Π°ΠΌ-ΠΊΠ°Π½Π°Π»Π΅ Β«Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° Ρ„Ρ€ΠΎΠ½Ρ‚Π΅Π½Π΄Π΅Ρ€Π°Β»

ВрСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

O(1) β€” константноС врСмя

ΠšΠΎΠ½ΡΡ‚Π°Π½Ρ‚Π½ΠΎΠ΅ врСмя выполнСния ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π½Π΅ зависит ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. ВрСмя выполнСния остаСтся постоянным, нСзависимо ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ, сколько элСмСнтов содСрТит массив ΠΈΠ»ΠΈ ΠΊΠ°ΠΊ ΠΌΠ½ΠΎΠ³ΠΎ Π΄Π°Π½Π½Ρ‹Ρ… ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Π΅Ρ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ. Π­Ρ‚ΠΎ происходит ΠΏΠΎΡ‚ΠΎΠΌΡƒ, Ρ‡Ρ‚ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ выполняСт фиксированноС количСство ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ, Π½Π΅ зависящих ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…:

   ΠšΠΎΠ½ΡΡ‚Π°Π½Ρ‚Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ
ΠšΠΎΠ½ΡΡ‚Π°Π½Ρ‚Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ константного Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния ΠΌΠΎΠΆΠ΅Ρ‚ ΡΠ»ΡƒΠΆΠΈΡ‚ΡŒ опСрация доступа ΠΊ элСмСнту массива ΠΏΠΎ индСксу. НапримСр, Ссли Ρƒ вас Π΅ΡΡ‚ΡŒ массив friends ΠΈ Π²Ρ‹ Ρ…ΠΎΡ‚ΠΈΡ‚Π΅ вывСсти Ρ‡Π΅Ρ‚Π²Π΅Ρ€Ρ‚Ρ‹ΠΉ элСмСнт массива, нСзависимо ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ, сколько элСмСнтов содСрТит массив, врСмя выполнСния этой ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ останСтся постоянным β€” ΠΏΠΎΡ‚ΠΎΠΌΡƒ, Ρ‡Ρ‚ΠΎ для доступа ΠΊ элСмСнту массива ΠΏΠΎ индСксу трСбуСтся Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½Ρƒ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ, которая Π½Π΅ зависит ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° массива:

Π‘Ρ‚Π°Ρ‚ΡŒΡ ΠΏΠΎ Ρ‚Π΅ΠΌΠ΅

πŸ“ˆ Big O нотация: Ρ‡Ρ‚ΠΎ это Ρ‚Π°ΠΊΠΎΠ΅ ΠΈ ΠΏΠΎΡ‡Π΅ΠΌΡƒ Π΅Π΅ ΠΎΠ±ΡΠ·Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ Π½ΡƒΠΆΠ½ΠΎ Π·Π½Π°Ρ‚ΡŒ ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡƒ программисту

O(log n) β€” логарифмичСскоС врСмя

ЛогарифмичСскоС врСмя выполнСния ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° увСличиваСтся ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ Π»ΠΎΠ³Π°Ρ€ΠΈΡ„ΠΌΡƒ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΎΡ‡Π΅Π½ΡŒ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ:

   ЛогарифмичСская ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ
ЛогарифмичСская ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° с логарифмичСским Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ выполнСния ΠΌΠΎΠΆΠ΅Ρ‚ ΡΠ»ΡƒΠΆΠΈΡ‚ΡŒ Π±ΠΈΠ½Π°Ρ€Π½Ρ‹ΠΉ поиск. Π’ Π±ΠΈΠ½Π°Ρ€Π½ΠΎΠΌ поискС ΠΌΡ‹ Π΄Π΅Π»ΠΈΠΌ массив ΠΏΠΎΠΏΠΎΠ»Π°ΠΌ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ шагС, ΠΏΠΎΠΊΠ° Π½Π΅ Π½Π°ΠΉΠ΄Π΅ΠΌ искомый элСмСнт. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, количСство шагов, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΡ‹Ρ… для поиска, растСт логарифмичСски ΠΏΠΎ ΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΡŽ ΠΊ Ρ€Π°Π·ΠΌΠ΅Ρ€Ρƒ массива.

Π’ΠΎΡ‚ простой ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π½Π° JavaScript, которая ΠΈΠΌΠ΅Π΅Ρ‚ логарифмичСскоС врСмя выполнСния:

Ѐункция logNFunc Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ Ρ‚Π°ΠΊ:

Π’ΠΎ Π΅ΡΡ‚ΡŒ ΠΌΡ‹ достигли 1 всСго Π·Π° 3 шага. Алгоритмы с логарифмичСским Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ выполнСния ΠΎΡ‡Π΅Π½ΡŒ эффСктивны: ΠΎΠ½ΠΈ ΠΌΠΎΠ³ΡƒΡ‚ ΠΎΠ±Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ большиС ΠΎΠ±ΡŠΠ΅ΠΌΡ‹ Π΄Π°Π½Π½Ρ‹Ρ… с ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ нСбольшим ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠ΅ΠΌ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния. На Π³Ρ€Π°Ρ„ΠΈΠΊΠ΅, ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΌ Π²Ρ‹ΡˆΠ΅, Π²ΠΈΠ΄Π½ΠΎ, Ρ‡Ρ‚ΠΎ Π½Π° Π±ΠΎΠ»ΡŒΡˆΠΈΡ… числах кривая становится всС Π±ΠΎΠ»Π΅Π΅ ΠΈ Π±ΠΎΠ»Π΅Π΅ плоской, большС напоминая ΠΏΡ€ΡΠΌΡƒΡŽ константного Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ.

O(n) β€” Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ΅ врСмя

Π­Ρ‚ΠΎΡ‚ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ ΠΌΡ‹ ΡƒΠΆΠ΅ рассматривали Π²Ρ‹ΡˆΠ΅, Π² ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ с ΠΏΠ°Ρ†ΠΈΠ΅Π½Ρ‚Π°ΠΌΠΈ стоматолога. ЛинСйная врСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° растСт прямо ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€Ρƒ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… β€” Ссли Ρ€Π°Π·ΠΌΠ΅Ρ€ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… увСличиваСтся Π² 6 Ρ€Π°Π·, врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Ρ‚Π°ΠΊΠΆΠ΅ увСличится Π² 6 Ρ€Π°Π·:

   ЛинСйная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ
ЛинСйная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° с Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠΉ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ ΠΌΠΎΠΆΠ΅Ρ‚ ΡΠ»ΡƒΠΆΠΈΡ‚ΡŒ простой Ρ†ΠΈΠΊΠ», ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ Ρ‡Π΅Ρ€Π΅Π· ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ элСмСнт массива. НапримСр, ΠΊΠ°ΠΊ Π² этой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ:

Алгоритмы с Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠΉ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ Ρ‚ΠΎΠΆΠ΅ ΡΡ‡ΠΈΡ‚Π°ΡŽΡ‚ΡΡ ΠΎΡ‡Π΅Π½ΡŒ эффСктивными, хотя, ΠΊΠ°ΠΊ ΠΎΡ‡Π΅Π²ΠΈΠ΄Π½ΠΎ, ΠΏΡ€ΠΈ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ ΠΎΡ‡Π΅Π½ΡŒ Π±ΠΎΠ»ΡŒΡˆΠΈΡ… объСмов Π΄Π°Π½Π½Ρ‹Ρ… ΠΎΠ½ΠΈ ΡƒΡΡ‚ΡƒΠΏΠ°ΡŽΡ‚ Π² эффСктивности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌ с логарифмичСским Π²Ρ€Π΅ΠΌΠ΅Π½Π΅ΠΌ выполнСния.

O(n log n) β€” Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ-логарифмичСскоС врСмя

Если ΠΎΠ±ΡŠΠ΅Π΄ΠΈΠ½ΠΈΡ‚ΡŒ послСдниС Π΄Π²Π΅ Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ слоТности (Π»ΠΎΠ³Π°Ρ€ΠΈΡ„ΠΌΠΈΡ‡Π΅ΡΠΊΡƒΡŽ ΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΡƒΡŽ), ΠΌΡ‹ ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ-логарифмичСскоС врСмя, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ ΠΈΠ½ΠΎΠ³Π΄Π° Ρ‚Π°ΠΊΠΆΠ΅ Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ псСвдолинСйным. Π’Π°ΠΊΠΎΠ΅ врСмя выполнСния часто встрСчаСтся Π² Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°Ρ…, основанных Π½Π° стратСгии «раздСляй ΠΈ властвуй» β€” сортировка слияниСм, быстрая сортировка ΠΈ сортировка ΠΊΡƒΡ‡Π΅ΠΉ.

Рассмотрим ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Ρ‚Π°ΠΊΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°:

Π‘Π½Π°Ρ‡Π°Π»Π° ΠΌΡ‹ создаСм ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ temp ΠΈ присваиваСм Π΅ΠΉ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ n, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡΠΊΠΎΠΏΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ n Π² temp. Π—Π°Ρ‚Π΅ΠΌ ΠΌΡ‹ Π½Π°Ρ‡ΠΈΠ½Π°Π΅ΠΌ Ρ†ΠΈΠΊΠ» while, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ ΠΌΡ‹ Π΄Π΅Π»ΠΈΠΌ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ n ΠΏΠΎΠΏΠΎΠ»Π°ΠΌ. На ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ строкС Ρƒ нас Π΅ΡΡ‚ΡŒ Ρ†ΠΈΠΊΠ» for, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ итСрируСтся temp Ρ€Π°Π·. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, врСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ внСшнСго Ρ†ΠΈΠΊΠ»Π° Ρ€Π°Π²Π½Π° O(log n), Π° Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½Π΅Π³ΠΎ O(n):

-8

Π˜Ρ‚ΠΎΠ³ΠΎΠ²Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π±ΡƒΠ΄Π΅Ρ‚ Ρ€Π°Π²Π½Π° O(n log n):

Как Π²ΠΈΠ΄Π½ΠΎ ΠΏΠΎ Π³Ρ€Π°Ρ„ΠΈΠΊΡƒ, ΠΏΡ€ΠΈ Π±ΠΎΠ»ΡŒΡˆΠΈΡ… ΠΎΠ±ΡŠΠ΅ΠΌΠ°Ρ… Π΄Π°Π½Π½Ρ‹Ρ… логарифмичСская Ρ‡Π°ΡΡ‚ΡŒ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ растСт довольно ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ, ΠΈ Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠ΅ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния происходит ΠΏΠΎΡ‡Ρ‚ΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ:

   Π›ΠΈΠ½Π΅ΠΉΠ½ΠΎ-логарифмичСская ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ
Π›ΠΈΠ½Π΅ΠΉΠ½ΠΎ-логарифмичСская ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

Π›ΠΈΠ½Π΅ΠΉΠ½ΠΎ-логарифмичСскоС врСмя β€” послСдний класс слоТности, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ считаСтся ΠΎΡ‡Π΅Π½ΡŒ эффСктивным: всС ΠΏΠΎΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ Ρ‚ΠΈΠΏΡ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Ρ€Π°Π±ΠΎΡ‚Π°ΡŽΡ‚ Π³ΠΎΡ€Π°Π·Π΄ΠΎ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅.

O(n^2) β€” ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎΠ΅ врСмя

ΠšΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½Π°Ρ врСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° увСличиваСтся ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚Ρƒ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…: Ссли Ρ€Π°Π·ΠΌΠ΅Ρ€ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… удваиваСтся, врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° увСличится Π² Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ Ρ€Π°Π·Π°. ΠŸΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² с ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎΠΉ Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ ΡΠ²Π»ΡΡŽΡ‚ΡΡ нСэффСктивныС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ сортировки β€” ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠ²Π°Ρ сортировка, сортировка вставками ΠΈ сортировка Π²Ρ‹Π±ΠΎΡ€ΠΎΠΌ.

Рассмотрим Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅:

Π­Ρ‚Π° функция ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Π΅Ρ‚ n Π² качСствС Π°Ρ€Π³ΡƒΠΌΠ΅Π½Ρ‚Π°. Π’Π½Π΅ΡˆΠ½ΠΈΠΉ Ρ†ΠΈΠΊΠ» Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ n Ρ€Π°Π·, Π³Π΄Π΅ каТдая итСрация Π±ΡƒΠ΄Π΅Ρ‚ Π²ΠΊΠ»ΡŽΡ‡Π°Ρ‚ΡŒ Π² сСбя Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½Π΅Π³ΠΎ Ρ†ΠΈΠΊΠ»Π°. Π’Π½ΡƒΡ‚Ρ€Π΅Π½Π½ΠΈΠΉ Ρ†ΠΈΠΊΠ» Ρ‚Π°ΠΊΠΆΠ΅ Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ n Ρ€Π°Π·:

-10

Π­Ρ‚Π° ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π° состоит ΠΈΠ· 4 строк ΠΈ 4 столбцов, ΠΏΠΎΡ‚ΠΎΠΌΡƒ Ρ‡Ρ‚ΠΎ n Π² нашСм ΠΊΠΎΠ΄Π΅ Π±Ρ‹Π»ΠΎ Ρ€Π°Π²Π½ΠΎ 4. ΠŸΠΎΠ΄ΡΡ‡ΠΈΡ‚Π°Π΅ΠΌ количСство шагов, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΡ‹Ρ… для Π²Ρ‹Π²ΠΎΠ΄Π° ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Ρ‹ 8Ρ…8:

Как Π²ΠΈΠ΄Π½ΠΎ ΠΏΠΎ Π³Ρ€Π°Ρ„ΠΈΠΊΡƒ, врСмя выполнСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ растСт Π³ΠΎΡ€Π°Π·Π΄ΠΎ быстрСС, Ρ‡Π΅ΠΌ Ρƒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° с Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ-логарифмичСской ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ:

   ΠšΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ
ΠšΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

O(2^n) β€” ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ врСмя

Π­ΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½Π°Ρ врСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° увСличиваСтся ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎ: Π΄Π°ΠΆΠ΅ нСбольшоС ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠ΅ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ Π·Π½Π°Ρ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΌΡƒ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΡŽ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния.

Рассмотрим Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ fib(n), которая вычисляСт числа Π€ΠΈΠ±ΠΎΠ½Π°Ρ‡Ρ‡ΠΈ с использованиСм рСкурсии. Π’ этой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ числа n Π²Ρ‹Π·Ρ‹Π²Π°ΡŽΡ‚ΡΡ Π΄Π²Π΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ fib(n β€” 1) ΠΈ fib(n β€” 2) :

Π­Ρ‚ΠΎ ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ Ρ‚ΠΎΠΌΡƒ, Ρ‡Ρ‚ΠΎ количСство Π²Ρ‹Π·ΠΎΠ²ΠΎΠ² Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ удваиваСтся Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡƒΡ€ΠΎΠ²Π½Π΅ рСкурсии. НапримСр, Π½Π° ΠΏΠ΅Ρ€Π²ΠΎΠΌ ΡƒΡ€ΠΎΠ²Π½Π΅ функция вызываСтся Π΄Π²Π° Ρ€Π°Π·Π°, Π½Π° Π²Ρ‚ΠΎΡ€ΠΎΠΌ ΡƒΡ€ΠΎΠ²Π½Π΅ β€” Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ Ρ€Π°Π·Π°, Π½Π° Ρ‚Ρ€Π΅Ρ‚ΡŒΠ΅ΠΌ ΡƒΡ€ΠΎΠ²Π½Π΅ β€” восСмь Ρ€Π°Π· ΠΈ Ρ‚Π°ΠΊ Π΄Π°Π»Π΅Π΅:

   РСкурсивноС вычислСниС ряда Π€ΠΈΠ±ΠΎΠ½Π°Ρ‡Ρ‡ΠΈ
РСкурсивноС вычислСниС ряда Π€ΠΈΠ±ΠΎΠ½Π°Ρ‡Ρ‡ΠΈ

ВрСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ этой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ составляСт O(2^n), ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ количСство Π²Ρ‹Π·ΠΎΠ²ΠΎΠ² Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ удваиваСтся Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡƒΡ€ΠΎΠ²Π½Π΅ рСкурсии, Ρ‡Ρ‚ΠΎ Π΄Π΅Π»Π°Π΅Ρ‚ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ нСэффСктивной для Π±ΠΎΠ»ΡŒΡˆΠΈΡ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ n. Π’ Ρ†Π΅Π»ΠΎΠΌ, Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ с ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ Π½Π΅ΠΏΡ€ΠΈΠ³ΠΎΠ΄Π½Ρ‹ для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с большими объСмами Π΄Π°Π½Π½Ρ‹Ρ…:

   Π­ΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ
Π­ΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

O(n!) β€” Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ врСмя

Π€Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ врСмя ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΈΡ‚ для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… Π·Π°Π΄Π°Ρ‡ Π΄Π°ΠΆΠ΅ мСньшС, Ρ‡Π΅ΠΌ ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΎΠ½ΠΎ увСличиваСтся Π³ΠΎΡ€Π°Π·Π΄ΠΎ быстрСС.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° с Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π»ΡŒΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ β€” функция, которая пытаСтся Π½Π°ΠΉΡ‚ΠΈ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ пСрСстановки Π½Π°Π±ΠΎΡ€Π° элСмСнтов:

ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ Ρ‚Π°ΠΊΠΈΡ… пСрСстановок растСт Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π»ΡŒΠ½ΠΎ, Ρ‡Ρ‚ΠΎ Π΄Π΅Π»Π°Π΅Ρ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΠΎ Π½Π΅ΠΏΡ€ΠΈΠ³ΠΎΠ΄Π½Ρ‹ΠΌ для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с большими объСмами Π΄Π°Π½Π½Ρ‹Ρ…:

-14

O(m+n) ΠΈΠ»ΠΈ O(mn)

ВсС рассмотрСнныС Π²Ρ‹ΡˆΠ΅ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Π»ΠΈ лишь ΠΎΠ΄ΠΈΠ½ Π²Ρ…ΠΎΠ΄Π½ΠΎΠΉ ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€. Но Ρ‡Ρ‚ΠΎ, Ссли Ρ‚Π°ΠΊΠΈΡ… ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ΠΎΠ² Π±ΡƒΠ΄Π΅Ρ‚ большС? Π’ ΠΎΠ±Ρ‰Π΅ΠΌ случаС, Ссли имССтся Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ с нСсколькими Π²Ρ…ΠΎΠ΄Π½Ρ‹ΠΌΠΈ ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€Π°ΠΌΠΈ, Π΅Π³ΠΎ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ опрСдСляСтся ΠΊΠ°ΠΊ функция ΠΎΡ‚ этих ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ΠΎΠ²:

  • Если ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π²Ρ…ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€Π°, ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π±ΡƒΠ΄Π΅Ρ‚ суммой ΠΈΡ… Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠ², O(m + n).
  • Если ΠΆΠ΅ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ Π²Π»ΠΎΠΆΠ΅Π½Ρ‹ Π΄Ρ€ΡƒΠ³ Π² Π΄Ρ€ΡƒΠ³Π° (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Π΅ Ρ†ΠΈΠΊΠ»Ρ‹), ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΡ€ΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ΠΌ ΠΈΡ… Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠ², O(mn).

О(m + n) ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° зависит ΠΎΡ‚ суммы Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠ² Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… m ΠΈ n:

Π’ этом ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ Ρ†ΠΈΠΊΠ» выполняСтся m Ρ€Π°Π·, Π° Π²Ρ‚ΠΎΡ€ΠΎΠΉ β€” n Ρ€Π°Π·. Π‘Π»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, ΠΎΠ±Ρ‰Π΅Π΅ врСмя выполнСния Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ суммС m + n. Π­Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° являСтся Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠΉ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΈΠ· Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ΠΎΠ² ΠΈ общая ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Ρ€Π°Π²Π½Π° O(m + n).

О(mn) ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ врСмя выполнСния Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° зависит ΠΎΡ‚ произвСдСния Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠ² Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… m ΠΈ n:

Π—Π΄Π΅ΡΡŒ Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½ΠΈΠΉ Ρ†ΠΈΠΊΠ» выполняСтся n Ρ€Π°Π· для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ внСшнСго Ρ†ΠΈΠΊΠ»Π°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ выполняСтся m Ρ€Π°Π·. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, ΠΎΠ±Ρ‰Π΅Π΅ количСство ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ, выполняСмых Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠ΅ΠΉ, Ρ€Π°Π²Π½ΠΎ m * n. Π‘Π»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° являСтся ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎΠΉ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ΠΎΠ² ΠΈ общая ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Ρ€Π°Π²Π½Π° O(mn).

ΠŸΡ€ΠΎΡΡ‚Ρ€Π°Π½ΡΡ‚Π²Π΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

Π­Ρ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² опрСдСляСтся Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΏΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ выполнСния, Π½ΠΎ ΠΈ ΠΏΠΎ ΠΎΠ±ΡŠΠ΅ΠΌΡƒ использованной памяти (пространства Π² Ρ‚Π΅Ρ€ΠΌΠΈΠ½ΠΎΠ»ΠΎΠ³ΠΈΠΈ большого О).

O(1) β€” константноС пространство

ΠšΠΎΠ½ΡΡ‚Π°Π½Ρ‚Π½Π°Ρ пространствСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ количСство памяти, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ, Π½Π΅ зависит ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Π’ этом ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π΄Π²Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ…: n ΠΈ result. НСзависимо ΠΎΡ‚ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° n, количСство памяти, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΠΎΠ΅ этой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠ΅ΠΉ, остаСтся постоянным:

O(log n) β€” логарифмичСскоС пространство

ΠŸΡ€ΠΎΡΡ‚Ρ€Π°Π½ΡΡ‚Π²Π΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ O(log n) ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ количСство памяти, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ, растСт логарифмичСски с ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠ΅ΠΌ Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Π’ этом ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ Π±ΠΈΠ½Π°Ρ€Π½Ρ‹ΠΉ поиск, ΠΈ с ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠ΅ΠΉ Ρ†ΠΈΠΊΠ»Π° Ρ€Π°Π·ΠΌΠ΅Ρ€ Π΄Π°Π½Π½Ρ‹Ρ… ΡƒΠΌΠ΅Π½ΡŒΡˆΠ°Π΅Ρ‚ΡΡ Π²Π΄Π²ΠΎΠ΅:

O(n) β€” Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ΅ пространство

ЛинСйная пространствСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ количСство памяти, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ, увСличиваСтся ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€Ρƒ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…:

O(n^2) β€” ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎΠ΅ пространство

Алгоритмы с ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎΠΉ пространствСнной ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ объСм памяти, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ растСт ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎ ΠΏΠΎ ΠΌΠ΅Ρ€Π΅ увСличСния Ρ€Π°Π·ΠΌΠ΅Ρ€Π° Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€ΠΎΡΡ‚Ρ€Π°Π½ΡΡ‚Π²Π΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ этого ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π° составляСт O(n^2), ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Π² Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ создаСтся ΠΌΠ°Ρ‚Ρ€ΠΈΡ†Π°, Ρ€Π°Π·ΠΌΠ΅Ρ€ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Ρ€Π°Π²Π΅Π½ n^2:

ПодвСдСм ΠΈΡ‚ΠΎΠ³ΠΈ

ΠšΠΎΠ½Ρ†Π΅ΠΏΡ†ΠΈΡ большого «О» ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΠΎΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ слоТной Π½Π° ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ взгляд, Π½ΠΎ Ρ€Π°Π·ΠΎΠ±Ρ€Π°Ρ‚ΡŒΡΡ Π² Π½Π΅ΠΉ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ: Π½Π°ΠΈΠ²Π½Ρ‹ΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ ΠΊ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ Π·Π°Π΄Π°Ρ‡ Π·Π°Ρ‡Π°ΡΡ‚ΡƒΡŽ ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ Ρ‡Ρ€Π΅Π·ΠΌΠ΅Ρ€Π½ΠΎ высокой Π²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΈ/ΠΈΠ»ΠΈ пространствСнной слоТности, Ρ‡Ρ‚ΠΎ Π΄Π΅Π»Π°Π΅Ρ‚ Ρ‚Π°ΠΊΠΈΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π½Π΅ΠΏΡ€Π°ΠΊΡ‚ΠΈΡ‡Π½Ρ‹ΠΌΠΈ для использования Π² Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… ΠΌΠ°ΡΡˆΡ‚Π°Π±Π½Ρ‹Ρ… ΠΏΡ€ΠΎΠ΅ΠΊΡ‚Π°Ρ…. Но Π²Ρ‹Ρ…ΠΎΠ΄ Π΅ΡΡ‚ΡŒ:

  • НСсмотря Π½Π° Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ для всСстороннСй ΠΎΡ†Π΅Π½ΠΊΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΈ Π²Ρ‹Π±ΠΎΡ€Π° ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌ Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ матСматичСский Π°Π½Π°Π»ΠΈΠ·, ΠΏΡ€ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΈ ΡƒΠΌΠ΅Ρ€Π΅Π½Π½ΠΎ слоТных Π·Π°Π΄Π°Ρ‡ часто достаточно ΠΎΡ†Π΅Π½ΠΊΠΈ Β«Π½Π° Π³Π»Π°Π·Β». НапримСр, Ссли ΠΊΠΎΠ΄ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Π΅ Ρ†ΠΈΠΊΠ»Ρ‹, навСрняка Π΅Π³ΠΎ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π±ΡƒΠ΄Π΅Ρ‚ ΠΊΠ²Π°Π΄Ρ€Π°Ρ‚ΠΈΡ‡Π½ΠΎΠΉ, Π° с ΠΊΠ°ΠΆΠ΄Ρ‹ΠΌ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΌ Ρ†ΠΈΠΊΠ»ΠΎΠΌ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π±ΡƒΠ΄Π΅Ρ‚ ΡƒΠ²Π΅Π»ΠΈΡ‡ΠΈΠ²Π°Ρ‚ΡŒΡΡ. Если ΠΆΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ Ρ€Π΅ΠΊΡƒΡ€ΡΠΈΡŽ с нСсколькими Π²Ρ‹Π·ΠΎΠ²Π°ΠΌΠΈ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡƒΡ€ΠΎΠ²Π½Π΅, Ρ‚ΠΎ, скорСС всСго, Ρ€Π΅Ρ‡ΡŒ ΠΈΠ΄Π΅Ρ‚ ΠΎΠ± ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠΉ слоТности.
  • Π˜Π½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ° ΠΈ ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠ° Ρ€Π°ΡΠΏΠΎΠ»Π°Π³Π°ΡŽΡ‚ Π±ΠΎΠ³Π°Ρ‚Π΅ΠΉΡˆΠΈΠΌ наслСдиСм ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² β€” Π²Ρ‹Π΄Π°ΡŽΡ‰ΠΈΠ΅ΡΡ ΡƒΠΌΡ‹ ΡƒΠΆΠ΅ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π»ΠΈ максимально эффСктивныС Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ для ΡˆΠΈΡ€ΠΎΠΊΠΎΠ³ΠΎ спСктра Π·Π°Π΄Π°Ρ‡. Π˜Π·ΡƒΡ‡Π΅Π½ΠΈΠ΅ ΠΈ ΠΏΠΎΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅ этих Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², Π° Ρ‚Π°ΠΊΠΆΠ΅ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠΎΠ², Π»Π΅ΠΆΠ°Ρ‰ΠΈΡ… Π² ΠΈΡ… основС, ΠΆΠΈΠ·Π½Π΅Π½Π½ΠΎ Π²Π°ΠΆΠ½ΠΎ для любого ΠΏΡ€ΠΎΡ„Π΅ΡΡΠΈΠΎΠ½Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠ°.

Π˜Π½Π²Π΅ΡΡ‚ΠΈΡ€ΡƒΡ врСмя Π² ΠΏΠΎΠ½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ слоТности ΠΈ ΠΈΠ·ΡƒΡ‡Π΅Π½ΠΈΠ΅ ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΡ… ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ ΠΏΡ€ΠΈΠΎΠ±Ρ€Π΅Ρ‚Π°ΡŽΡ‚ ΡΠΏΠΎΡΠΎΠ±Π½ΠΎΡΡ‚ΡŒ ΡΠΎΠ·Π΄Π°Π²Π°Ρ‚ΡŒ Π΄Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅, ΠΌΠ°ΡΡˆΡ‚Π°Π±ΠΈΡ€ΡƒΠ΅ΠΌΡ‹Π΅ ΠΈ рСсурсоэффСктивныС систСмы, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΠΎΠ³ΡƒΡ‚ ΡΠΏΡ€Π°Π²Π»ΡΡ‚ΡŒΡΡ с самыми слоТными Π·Π°Π΄Π°Ρ‡Π°ΠΌΠΈ Π² Ρ€Π΅Π°Π»ΡŒΠ½ΠΎΠΌ ΠΌΠΈΡ€Π΅.

***

ΠŸΡ€ΠΈ ΠΏΠΎΠ΄Π³ΠΎΡ‚ΠΎΠ²ΠΊΠ΅ ΡΡ‚Π°Ρ‚ΡŒΠΈ использовалась публикация Big O Notation: A Simple Explanation With Examples.

Наука
7 ΠΌΠ»Π½ ΠΈΠ½Ρ‚Π΅Ρ€Π΅ΡΡƒΡŽΡ‚ΡΡ