정수의 배열에

최고 로그 (N) 또는 (n)의 상단 SQT 찾기 무엇을 의미하는지 이해 하는가 정수 배열에 값을 값을 최고 로그 (N) 또는 (n)의 상단 SQT 찾기 선형 시간보다 적습니다.

그렇지 않으면 질문은 http://www.careercup.com/question?id=9337669입니다.

이 질문에 대한 이해를 돕고 나서 해결 될 수 있습니까? (비록 내가 이해할지라도 그것을 해결할 수도 있음)

시간 내 주셔서 감사합니다. 당신이 모든 요소를 읽을 필요가 있기 때문에 배열을 가정

2011-12-21 Aj Gauravdeep

는,이 문제는 Omega(n)입니다, 정렬되지 않습니다 [최대 비 정렬 된 배열에 Omega(n) 문제가 발견,이 문제는 최대를 발견 한 후 쉽게되지 않습니다]. 그래서, 거기에 대한 sublinear 솔루션이 없습니다.

배열 속는를 포함하지만, 제 2 단계에 속는 트리밍 비교적 쉬운 경우 의사 코드가 정확하지 selection algorithm

1. find the log(n) biggest element. //or sqrt(n) biggest element... 
2. scan the array and return all elements bigger/equal it.

(*)를 사용 O(n) [선형] 용액이있다.

출처

2011-12-21 08:18:54 amit

설명해 주셔서 감사합니다. Amit. 나는이 "배열을 스캔하고 모든 요소를 더 크거나 같게 반환했다"는 것을 이해할 수 없었다. '여기'가 무슨 뜻이야? 내가 분명히 이해한다면 이 질문은 array> top log (n) 또는 top sqt (n)에있는 모든 요소를 반환하겠습니까? 위의 Emilio는 sqt [배열의 가장 큰 요소]를 반환하기를 원한다고 언급했습니다. –

'it'은 (1) 단계에서 찾은 요소입니다. 'top log (n) 또는 top sqt (n) 값을 찾는다. '와 ** not **를 나타 내기 때문에이 질문은'log (n)/sqrt (n)'보다 큰 모든 값을 요구한다. '최상위 로그 (n) 또는 최고 sqt (n) 값 찾기'[[값 ** s **가 아닌 값을 묻습니다]] – amit

아줌마. 고마워요. –

정렬되지 않은 배열의 경우 복잡성은 선형이지만 log (n) 및 sqrt (n)이 모두 단조 증가 함수이므로 최대 (log (n), ..)를 관찰하여 성능을 향상시킬 수 있습니다. .) 또한 log (max (n, ...))이며 sqrt에 대해서도 동일합니다.

그래서 max (n) (선형)을 찾고 log와 sqrt를 계산하십시오.

출처

2011-12-21 08:50:16

물론 우리는 0이 아닌 양의 정수를 가정합니다. –

@ edA-qamort-ora-y : 사실이지만 최고 가치를 찾기 위해 "속도"에 관심이 없습니다. –

질문을 이해합니다. 감사. –

정수의 배열에

답변

관련 문제