gifht
ohyao
plape
dreco
이런식으로 5글자 영단어가 순서가 랜덤으로 섞여있는걸
그 100배의 크기를 가진 Dictionary file 하고 비교해서
[Dictionary]
apple
beast
chair
coder
fight
hated
hater
kakao
panic
yahoo
(생략)
출력이
알파벳순으로
apple
coder
fight
yahoo
이렇게 하게 하려면
어떤 big O 시간이 걸릴까여
ohyao
plape
dreco
이런식으로 5글자 영단어가 순서가 랜덤으로 섞여있는걸
그 100배의 크기를 가진 Dictionary file 하고 비교해서
[Dictionary]
apple
beast
chair
coder
fight
hated
hater
kakao
panic
yahoo
(생략)
출력이
알파벳순으로
apple
coder
fight
yahoo
이렇게 하게 하려면
어떤 big O 시간이 걸릴까여
설리
저게 끝이라면. 영단어의 개수를 N, Dictionary 개수는 100N. 영단어는 모두 Dictionary에 들어있다고 가정. Binary Search => O(N * lg100N) = O(N * (lg100 + lgN)) = O(NlgN).
5글자니깐 비교하는 데 5의 time이 들지만 상수배기 때문에 생략.
그런데 단어가 랜덤 믹스 되있자낭 더걸리지 않으려나
예를들어 gifht 이거면 fight를 찾아야하는데?
Dictionary 읽어서 Dictionary에다가 있는 단어만 체크 표시해 놓고 마지막에 출력할 때 Dictionary 읽어서 O(100N) = O(N) 하면 되지. 랜덤하게 섞인 건 문제가 안 돼.
아 그런 거였어? 그건 셈 정렬 방식으로 count하면 되지.
hash(a의 개수, b의 개수, c의 개수, d의 개수, ..., z의 개수) + hash({출현 알파벳)} 정도로 hash화해서 비교하면 될 듯.
5의 time 대신에 좀 더 큰 상수배가 곱해진다는 것일 뿐. O(NlgN)임에는 변함이 없음.
와 솔직히 N^2까지 갈줄알았는데 앵간하면 n log n이군하
http://autogram.tk/이
중고차 어플리케이션 어떤가요?