Две части TCS - это алгоритмы и сложность. Я упрощенно скажу, что алгоритмы - это исследование верхних границ, показывающее, что вы можете что-то сделать (с заданными ограниченными ресурсами), а сложность заключается в том, чтобы показать, что вы не можете сделать это без каких-либо минимальных ресурсов.
Очень часто алгоритмическая проблема формулируется в модели решения, чтобы поместить ее в класс сложности.
Но меня всегда беспокоило то, что некоторые элементарные алгоритмы никогда не упоминаются как принадлежащие к определенному классу. Одним из примеров является (сравнение) сортировка. Попробуйте, как я мог бы, соответствующий класс кажется слишком неполноценным (на самом деле, он просто проверяет в лог-пространстве, что результат отсортирован? Это кажется слишком слабым, или я не понимаю верную версию решения).
Каков наилучший / наиболее подходящий / наиболее полезный класс сложности, в котором заключается сортировка сравнения?
Я считаю, что FP это то, что вы ищете.
источник