0
특정 조건이 채워지면 counting-sort는 선형 시간으로 정렬 할 수 있습니다. 시퀀스 A = < a1을 생성하십시오. : : :; a10>의 n = 10인데, 여기서 counting-sort는 theta (n^7) 시간이 필요합니다. 당신의 선택을 설명하십시오.소계 분류 - 어떻게 작동하는지는 알고 있지만 해결할 수 없음
내 접근 방식;
만약 내가 A = [0,0,0,1,2,3,4,5,6,2]를 선택하면, n = 10 C new는 [3,4,6,7,8 , 9,10]와 B = [0,0,0,1,2,2,3,4,5,6] 이것은 정렬 연산이 (강의에 따라) 어떻게 작동 하는지를 보여줍니다. n 전원 7의? 의사 코드에 따라 각 단계의 실행 시간을 계산 한 다음?
여기에 게시 된 질문과 같이 보입니다. – nullpointer
네, coz 제가 어떻게 정렬 작업을 알고 있고 아래와 같이 사용 해보았습니다. 내가 A = [0,0,0,1,2,3,4,5,6,2]를 선택하면 n = 10 C new는 [3,4,6,7,8,9, 10] 및 B = [0,0,0,1,2,2,3,4,5,6] 이것은 정렬 작업이 (강의에 따라) 작동하는 방식이지만 어떻게 n 시간의 실행 시간을 갖는지 증명할 수 있습니다 7? 의사 코드에 따라 각 단계의 실행 시간을 계산 한 다음? –
이 문제는 해결할 수없는 것처럼 보입니다. 왜냐하면 Theta 표기법은 n의 함수로 한계에서 런타임에 대해 말하기 때문에 런타임이 Theta (n^7) 인 고정 n 및 고정 시퀀스를 사용할 수 없어야합니다 . 고정 된 크기와 시퀀스의 경우 런타임은 O (1)입니다. – templatetypedef