2.1 Обчислювальна складність

2.1.1 Складність по часу виконання алгоритму

2.1.1.1 Оцінка розміру вхідних даних

2.1.1.2 Залежність часу виконання від розміру вхідних даних

2.1.1.3 Аналіз нерекурсивних алгоритмів

2.1.1.4 Аналіз рекурсивних алгоритмів

2.1.1.5 Аналіз алгоритму відповідно до варіантів його виконання: для найкращого випадку, для середнього випадку та для найгіршого випадку

2.1.1.6 Асимптотичний аналіз

2.1.1.6.1 Загальні визначення

2.1.1.6.2 Нотація Бахмана-Ландау (група асимптотичних нотацій): О-, о-, Ω-, ω-, Θ- нотації

2.1.1.7 Детермінований (DTIME) та недетермінований (NTIME) ресурси часу виконання

2.1.1.8 Здійсненні класи складності

2.1.1.8.1 DLONGTIME-клас складності (логарифмічний)

2.1.1.8.2 PolylogTIME-клас складності (полілогарифмічний)

2.1.1.8.3 P-клас складності (поліноміальний)

2.1.1.8.4 P-повні задачі

2.1.1.8.5 RP-клас та coRP-клас складності

2.1.1.8.6 ZPP-клас складності

2.1.1.8.7 BPP-клас складності

2.1.1.8.8 BQP-клас складності

2.1.1.9 Проблематичні класи складності

2.1.1.9.1 NP- та coNP- класи складності

2.1.1.9.2 Співвідношення між P- та NP- класами складності

2.1.1.9.3 NP- та coNP- повні задачі. Теорема Кука-Левіна. Стандартні NP-повні задачі.

2.1.1.9.4 NP- складні, еквівалентні, проміжні та прості задачі

2.1.1.9.5 PP-клас складності

2.1.1.9.6 UP-клас складності

2.1.1.9.7 #P-клас (вимовляється як «шарп П») складності та #P-повні задачі

2.1.1.9.8 ⊕P-клас (вимовляється як «паритет П») складності

2.1.1.10 Нездійсненні класи складності

2.1.1.10.1 EXPTIME-клас складності (експоненціальний клас складності)

2.1.1.10.2 NEXPTIME-клас складності

2.1.1.10.3 2-EXPTIME-клас складності

2.1.1.10.4 ELEMENTARY-клас складності

2.1.1.10.5 R-клас складності

2.1.1.10.6 PR-клас складності

2.1.1.10.7 RE-клас складності та coRE-клас складності

2.1.1.10.8 ALL-клас складності

2.1.1.11 Аналіз паралельних алгоритмів

2.1.1.11.1 Особливості аналізу паралельних алгоритмів

2.1.1.11.2 Теорема Брента. Закон Густавсона–Барсіса. Закон Амдала.

2.1.1.11.3 NC-клас складності

2.1.2 Ємнісна (просторова) складність алгоритму (складність по об’єму пам’яті)

2.1.2.1 Визначення просторової складності алгоритму

2.1.2.2 Детермінований(DSPACE) та недетермінований(NSPACE) просторові(ємнісні) ресурси

2.1.2.3 Теорема Севіча

2.1.2.4 Здійсненні класи складності

2.1.2.4.1 L-клас складності

2.1.2.4.2 PolyL-клас складності (полілогарифмічний)

2.1.2.4.3 SL-клас складності

2.1.2.4.4 NL-клас складності

2.1.2.4.5 NL-повні задачі

2.1.2.4.6 Еквівалентність класів NL та coNL

2.1.2.4.7 RL-клас складності

2.1.2.5 Проблематичні класи складності

2.1.2.5.1 PSPACE-клас складності

2.1.2.5.2 PSPACE-повні задачі

2.1.2.6 Нездійсненні класи складності

2.1.2.6.1 EXPSPACE-клас складності (експоненціальний клас складності по пам’яті)

2.2. Структурна складність

2.2.1 Цикломатична складність

2.2.1.1 Цикломатичне число

2.2.1.2 Цикломатична складність графу потоку керування та графу алгоритму

2.2.2 Структурна складність обчислень поданих структурною матрицею потокового графу алгоритму

2.2.3 ACⁱ-класи складності

2.2.4 ACC⁰-клас складності

2.2.5 TCⁱ-класи складності

2.2.6 CC-клас складності

2.3 Ієрархії класів складності

2.3.1 Теорема про ієрархії класів часової складності

2.3.2 Теорема про ієрархії класів просторової складності

2.3.3 Поліноміальна ієрархія та PH-клас складності

2.3.4 Експоненціальна ієрархія

2.3.5 Ієрархія Гжегорчика

2.3.6 Арифметична ієрархія

2.3.7 Булева ієрархія