역수를 계산하십시오.

-2

A[1...n]을 n 개의 다른 숫자로 구성된 배열로합시다.역수를 계산하십시오.

쌍 (i, j)은 인 인 경우 i < j and A [i] > A [j]이라고합니다.

예 :

A : = (2, 3, 8, 6, 1) => A가 5 역함수를 갖는다.

과제 : 배열 A [1..N 이러한 알고리즘의 복잡도가 있음 O (N * logn)의 역수의 수를 찾아내는

쓰기 프로그램.

출처

2016-10-22 Lê Bảo Châu

에 오신 것을 환영합니다 병합 정렬의 실행 시간입니다! 숙제 질문에는 노력과 현재 가지고있는 코드가 나와야합니다. 숙제 문제를 축 어적으로 버려서 좋은 반응을 얻지 못할 수도 있습니다. 당신이 고심하고있는 것을 설명하고 명확한 디버깅 정보를 제공하십시오. – Aurora0001

http://stackoverflow.com/a/40001355/1040597 – Tempux

이 문제는 병합 정렬을 기반으로 해결할 수 있습니다.

엄격히 말해서 merge(A, B) 프로 시저를 수정하여 (a, b) such that a in A, b in B and b > c 쌍 수를 반환해야합니다. 이 문제를 해결하는 데 필요한 실행 시간을 볼 수 있듯이

그러므로, 스택 오버플로 O(n * log(n))

출처

2016-10-22 17:22:32

나는 시도했지만 사실이 아니다. –

코드를 게시하여 솔루션 경로를 안내 할 수 있습니까? –

역수를 계산하십시오.

답변

관련 문제