![[레벨:0]](http://algospot.com/zbxe/modules/point/icons/default/0.gif "포인트:80point (88%), 레벨:0/30"){kind=icon}
상욱http://algospot.com/zbxe/?document_srl=5108
위의 에디토리얼을 보면.
4번 해법이 Suffix Array를 사용하는 해법이잖아요.
근데 이것의 복잡도가 O(n^2logn)인게 이해가 안되요. ㅜㅜ
정렬에 드는 시간은 O(nlogn) 아닌가요?
정렬은 한 번만 하면 되니까.
총 복잡도는 O(n^2 + nlogn) 이니까.
결과적인 복잡도는 O(n^2) 이 된다고 생각하는데...
O(n^2logn)이 되려면. 정렬을 n번 해야 하는데.
아무리 생각해도 정렬은 한 번만 하는게 아닌가... 생각이 들어서요.
덧, 그리고 여기 RSS가 접속이 안 되요. ㅜㅜ
![[레벨:2]](http://algospot.com/zbxe/modules/point/icons/default/2.gif "포인트:605point (54%), 레벨:2/30"){kind=icon}
김우현![[레벨:1]](http://algospot.com/zbxe/modules/point/icons/default/1.gif "포인트:90point (0%), 레벨:1/30"){kind=icon}
Dynamical![[레벨:5]](http://algospot.com/zbxe/modules/point/icons/default/5.gif "포인트:2430point (18%), 레벨:5/30"){kind=icon}
Being
실제 정렬하는데 드는 복잡도는 O( N*logN * '두 element를 비교하는데 걸리는 시간')
이 대략 걸립니다. 보통은 int형을 정렬하기 때문에 O( N*logN * 1) 로 간주하는거죠.
문자열은 대소관계를 비교하는데 O(N) 시간이 걸리기 때문에
O(N * logN * N) => O(N^2 * logN) 이 걸리게 됩니다.