Какая сложность алгоритмов зависит от n или k и от чего она зависит

Что проверяют

Понимаете ли вы, что сложность это функция от всех параметров задачи, а не только от размера данных. В ML почти у каждого алгоритма есть второй параметр: число соседей, кластеров, фолдов, признаков. Следом обычно просят оценить конкретный случай, например top-k из миллиона скоров.

Как отвечать

Начните с того, что O-нотация описывает рост затрат при росте входа, и честная оценка включает каждый параметр, который меняется. Дальше примеры, где k меняет картину:

• top-k элементов: полная сортировка стоит O(n log n), куча размером k даёт O(n log k) (heapq.nlargest), а np.argpartition находит k лучших за O(n) без их упорядочивания;
• k-means: одна итерация стоит O(n·k·d), где d это число признаков, всего O(n·k·d·i). Забытое d в оценке типичная ошибка;
• kNN: обучение почти бесплатное, а предсказание перебором стоит O(n·d) на один запрос. KD-дерево ускоряет поиск на малой размерности, но при десятках признаков вырождается почти в перебор;
• k-fold кросс-валидация: стоимость обучения умножается на k, а при подборе по сетке ещё и на число комбинаций.

От чего зависит сложность, помимо n и k: от размерности d, от структуры данных (хэш-таблица против списка), от распределения входа (средний и худший случай быстрой сортировки). Пространственную сложность называйте отдельно: матрица попарных расстояний для n объектов занимает O(n²) и на сотне тысяч строк уже не помещается в память.

Где спотыкаются

Говорят, что распараллеливание снижает сложность. Оно сокращает время на часах, но суммарная работа остаётся той же: O(n·k·d) на восьми ядрах по-прежнему O(n·k·d).

Считают k константой и выбрасывают его из оценки. Для k = 10 это допустимо, для k порядка n уже нет: O(n log k) превращается в O(n log n).

Путают k в kNN и k в k-means и не называют, что обозначает буква. Прежде чем оценивать, скажите вслух, что такое n, k и d в этой задаче.