💻 Алгоритмдердің есептеу күрделілігі: ыңғайлы шпаргалка

Алгоритмдердің есептеу күрделілігін түсіну программист ​​үшін маңызды. Кем дегенде, олар жұмыс сұхбаты кезінде сұралуы мүмкін, ал былайша сіздің жобаңызды жақсартуға көмектеседі.

❓Бұл не?

Есептеу күрделілігі мынаған жауап беруге тырысады: кіріс деректерінің өлшеміне байланысты алгоритмнің орындалу уақыты мен бос тұрған жад көлемі қалай өзгереді? Мұнда асимптотикалық күрделілік деген ұғым енгізіледі. Бұл кіріс деректерінің өлшемі шексіздікке жақындаған кезде (орындау уақыты немесе жадты пайдалану сияқты) шектеулі ресурстардың әрекетін сипаттайтын математикалық модель. Асимптотикалық күрделілігі төмен алгоритм барлық кірістер үшін тиімдірек.

Алгоритмнің асимптотикалық күрделілігі үшін келесі белгілер қолданылады: 𝑂
(«O» - үлкен), ол уақыттың жоғарғы шегін сипаттайды.

✍️ 𝑂-белгідегі алгоритмдік күрделілік категориялары:

▶️ Тұрақты уақыт: 𝑂(1)
Орындау уақыты кіріс деректер жиынындағы элементтер санына байланысты емес.
▶️ Сызықтық уақыт: 𝑂(𝑁)
Орындау уақыты жиынтықтағы элементтер санына пропорционал.
▶️ Логарифмдік уақыт: 𝑂(log𝑁)
Орындау уақыты жиындағы элементтер санының логарифміне пропорционал.
▶️ Сызықтық-логарифмдік уақыт: 𝑂(𝑁log𝑁)
Орындау уақыты сызықтыдан үлкен, бірақ квадраттан аз.
▶️ Квадраттық уақыт: 𝑂(𝑁^2)
Орындау уақыты жиындағы элементтер санының квадратына пропорционал.

🔗 Керемет шпаргалкаға сілтеме (https://www.bigocheatsheet.com/)

#UsefulInfo 📚