글 읽기 - 시간복잡도 질문

이 문제가 디닉을 써야만 하는 문제로 나와있는데

디닉 알고리즘의 시간복잡도가 O(V^2 * E)인 것으로 알고 있습니다.

위 문제에서 간선이 대충 10만개라고 해도 25만 * 10만을 하면 너무 커지지 않나요?

네트워크 플로우 관련 문제들을 보면서 느끼는게 시간복잡도를 구하는게 너무 힘드네요 왜 디닉 알고리즘을 사용하면 시간복잡도가 맞는지 설명해주실 수 있나요?

다른 분 말씀을 옮기자면, 이런 문제들은 데이터를 worst case 에 맞춰서 빡빡하게 넣지 않는다고 합니다....

위 말을 들으니까 두 그룹으로 나뉜다고 생각해서 O((V/2)^4) == (250)^4 라고 본다면 그럴 수도 있겠다는 생각이 들었습니다.

위의 댓글은 "잘 나이들지 못했습니다." (Didn't age well)

1년 전 데이터 추가되었습니다.

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge