absorption time의 기대값 구하기는 동적계획법으로 O(V + E)에 가능한데
만약 DAG에서 정확히 한개의 간선을 골라서 제거 할 수 있을때 가능한 최대 기대값은 어떻게 효율적으로 구할까?
예를 들어서 정점 v에서 나가는 간선들 가중치가 0.7, 0.2, 0.1이라 했을때 0.2인 간선을 지우면 나머지 간선 가중치는 0.7 / 0.8, 0.1 / 0.8 임.
당연히 brute force로 하면 O((V + E) * E) 에 구할 수 있는데 이거보다 빨라야 함.
1.그래프 전체의 흡수시간 기대값을 구한다. 이 때 Vertex에 [해당 Vertex가 초기 상태일 경우의 흡수시간 기대값]를 같이 기록한다. O(V + E)
2.모든 Vertex를 순회하면서 해당 Vertex에서 나가는 Edge들 중에 하나씩을 제거한 후 나머지 Edge들로 기대값 재계산.(정확히는 델타를 구함) 이 델타를 이용해서 그래프 전체의 기대값 재계산 O(E^2)
3. 2에서 1의 정보를 이용할 수 있으므로 1은 한번만 수행 되면 됨. O(V+E) + O(E^2) = O(V + E + E^2) = O(E^2)
V <= E 라고 가정했을때 O(E * (V + E)) = O(VE + E^2) = O(E^2) 임. O(E^2) 방법은 쉬운데, 이것보다 더 빠른 방법이 궁금한거임. O(E log V) 같은거.
그니까 asymptotically faster algorithm
알았어 생각해볼게.