Мне нужно оценить временную сложность алгоритма решения «Задачи раскраски графиков», основанного на градиенте полулогарифмического графика зависимости времени выполнения от размера ввода.Ранее я должен был сделать то же самое для алгоритма сортировки вставкой.Я увидел следующее, чтобы найти временную сложность алгоритма сортировки вставкой, основанного на градиенте 2:
log(T(n)) / log(n) = 2
log(T(n)) = 2 * log(n)
log(T(n)) = log(n²)
T(n) = n²
Из того, что я прочитал, кажется, что алгоритмы, решающие проблему раскраски графа, обычно имеют экспоненциальное времясложность.
Вот график с линейной осью: 
, а вот график с логарифмической осью времени:
При сортировке вставкой я проигнорировал первую часть графика, поскольку он содержал много шума, и асимптотическую сложность по времени лучше всего увидеть при больших входах.Однако я предполагаю, что мне нужно посмотреть весь граф, чтобы найти временную сложность алгоритма решения задачи раскраски графа.Просто факт, что наклон меняется, я знаю, что это экспоненциально.Есть ли способ быть более точным и дать реальный ответ, как это было сделано выше для вставки сортировки?