글 읽기 - 시간 복잡도 어떤게 맞는건가요?

drwolf1999 6년 전 0

아래코드가 좌표평면에 임의의 여러개의 점에 모두 다른 색을 입히고 초당 십자방향으로 1만큼씩 퍼트릴때 인접하면 섞이는것을

이차원배열을 bfs하면서 색이 만날때마다 Union_find하는걸 대략적으로 한건데요 이렇게 되면 시간복잡도가

O(N^2 * M log(M))인가요 O(N^2 * log(M))인가요??

배열크기는 N * N이고 색의 가짓수는 M입니다

while (!que.empty()) {//bfs
    .
    .
    .
    .    
	if (find(visit[nx][ny]) != find(visit[x][y]))//Union_find
        Union(visit[x][y], visit[nx][ny]);
    .
    .
    .
    .
}

yukariko 6년 전 1

O(N^2lgM) 이맞는것 같습니다.

union find의 복잡도가 액커만 이라 거의 상수로 봐도 무방합니다만..

drwolf1999 6년 전 0

@yukariko 아 감사합니다!!

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

문제

문제

출처

ICPC

시간 복잡도 어떤게 맞는건가요?

drwolf1999 6년 전 0

yukariko 6년 전 1

drwolf1999 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말