Что считается кубическим алгоритмом при рассмотрении сложности времени?

Question

Итак, я реализовал этот алгоритм и, проанализировав его временную сложность, обнаружил, что его верхняя граница ограничена O(n^2*m), где n - количество вершин в графе, а m - количество ребер. Мне интересно, будет ли это рассматриваться как кубический алгоритм? Я знаю, что O(n^3) является кубическим, но из-за "m" я не уверен. Кто-нибудь может объяснить, если это кубический или какой-то другой тип сложности?

Answer 1

Графовые алгоритмы представляют собой особый случай, касающийся сложности времени. Технически O(n^2*m) является квартикой (O(n^4)), поскольку m = O(n^2). Однако, поскольку многие алгоритмы графов чувствительны к количеству ребер, мы сообщаем о сложности как функции от вершин и ребер отдельно, чтобы отразить эту чувствительность. Если граф является разреженным (с m = O(n)), то O(n^2m) является кубическим, но для более плотных графов он ведет себя больше как квартальный алгоритм.