형들 기수정렬 시간복잡도 질문좀

[익명(175.213)]

원소 n개를 r개의 버킷에 분배하는게 왜 n+r이야?
원소 8개 있다치면
버킷 고르는 연산 8번 대입 8 해서 16아님?

[0xrgb(0xrgb)]

원소 n개를 r개의 버킷에 분배하면 n이지

[익명(175.213)]

ㄴ 근데 ppt에서 분배하는게 n+r이라함...

[익명(175.213)]

아이고부장님 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ버킷ㅋㅋㅋ리스트ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

[0xrgb(0xrgb)]

아마 버킷에 있는거 다시 읽어와서 배열해야하니까 이거때문에 O(n+r) 인듯

[0xrgb(0xrgb)]

그러면 한 패스 돌때마다 O(n+r)이고 이걸 d번 하니까 O(d(n+r))

[익명(175.213)]

아 그러넹 ㅋㅋㅋㅋㅋ 바로 이해감 알려줘서고마워 ㄱㅅㄱㅅ