시간 복잡성을 고려할 때 큐빅 알고리즘으로 간주되는 것은 무엇입니까?

Question

그래서이 알고리즘을 구현했고 시간 복잡도를 분석 한 결과 O (n^2 * m)에 의해 상한이 제한된다는 것을 발견했습니다. 여기서 n은 그래프의 정점 수이고, m은 가장자리. 큐빅 알고리즘으로 간주 될지 궁금하네요? 나는 O (n^3)가 입방체라는 것을 압니다. 그러나 "m"때문에 나는 확실하지 않습니다. 입방체 또는 다른 유형의 복잡성인지 설명 할 수있는 사람은 누구입니까?

Answer 1

그래프 알고리즘은 m = O (n^2)이므로 기술적으로 O (n^2 * m)는 quartic (O (n^4))입니다. 그러나 많은 그래프 알고리즘이 에지 수에 민감하기 때문에 민감도를 반영하기 위해 정점과 에지의 함수로 복잡성을 별도로보고합니다. 그래프가 희박한 경우 (m = O (n)), O (n^2m)은 3 차이지만 밀도가 높은 그래프의 경우 4 차 알고리즘과 유사합니다.