Какая алгоритмическая сложность вычисления ROC-AUC

Вычисление ROC-AUC имеет сложность O(n log n) из-за необходимости сортировки предсказанных вероятностей (или scores) по убыванию. Основные шаги:

1. Сортировка данных — O(n log n)
2. Построение ROC-кривой — O(n) (проход по отсортированным данным)

Пример на Python с sklearn:

from sklearn.metrics import roc_auc_score
y_true = [0, 1, 1, 0]
y_scores = [0.1, 0.4, 0.35, 0.8]
roc_auc_score(y_true, y_scores)  # O(n log n)

Для небольших данных разница незаметна, но на больших датасетах (миллионы строк) сортировка становится узким местом.