작은 알고리즘으로 구성된 알고리즘의 큰 o 표기법

Question

그래프를 사용하는 과제를 사용하고 그래프에 대한 추가 버텍스를 추가하고 소스로 새로운 꼭지점으로 Bellman Ford를 적용한 다음 Dijkstra의 모든 쌍을 그래프에 적용합니다.

사용되는 알고리즘은 런타임 / 공간 요구 사항을 가지고 있습니다 :

Adding extra vertex
-- Running Time: V
-- Space: V
Bellman Ford single source shortest path algorithm
-- Running time: EV
-- Space: V
Dijkstra's all pairs shortest path algorithm
-- Running time: EV log V
-- Space: V

.

전체 프로세스의 큰 O를 계산하면 이해가 어려울 수 있습니다.각 프로그램은 개별적으로 실행되며 출력은 프로그램에서 프로그램까지 파이프됩니다.내 알고리즘은

의 빅 런타임 시간을 가질 것입니다.

o (v + ev + ev log v) o (ev log v)

공간 요구 사항은 유사한 방식으로 계산됩니다.나는 이것을 정확하게 생각하고 있니?감사합니다!

Answer 1

정확히 "엄지 손가락의 규칙"은 코드 블록의 시퀀스에서 전체 복잡성이 가장 큰 복잡성을 갖는 블록에 의해 지배된다는 것입니다.

matemally, v가 매우 큰 숫자가되면 evlogv보다 작 으면 EV보다 작습니다.따라서 대형 V의 경우 알고리즘의 복잡성은 evlogv

에 의해 잘 근사치됩니다.