주어진 배열에서 크기 3의 반전을 계산하는 JavaScript 프로그램

이 튜토리얼에서는 주어진 배열에서 크기 3의 반전을 계산하는 방법을 배웁니다.

문제 설명 - 서로 다른 숫자 항목을 포함하는 길이 n의 배열이 제공됩니다. arr[i] > arr[j] > arr[k]인 크기 3의 숫자 쌍의 총 개수를 찾아야 합니다. 여기서 I

여기에서는 먼저 무차별 대입 방법을 배운 다음 시간과 공간 복잡성을 최적화하겠습니다.

무차별적인 방법을 사용하세요

무차별 접근 방식에서는 세 개의 중첩 for 루프를 사용하여 크기 3의 반전 개수를 찾습니다. 첫 번째 루프는 1개 요소부터 n-2개 요소까지 반복되고, 두 번째 루프는 i번째 요소부터 n-1번째 요소까지 반복됩니다. 이전 요소가 다음 요소보다 크면 배열을 반복하여 중간 요소보다 작은 요소를 찾습니다.

문법

사용자는 아래 구문에 따라 무차별 대입 방법을 사용하여 주어진 배열에서 크기 3의 반전을 계산할 수 있습니다.

으아아아

알고리즘

• 1단계 - for 루프를 사용하여 첫 번째 n-2 요소를 반복합니다.

• 2단계 - 중첩된 for 루프를 사용하여 m+1에서 len-1 요소까지 반복합니다.

• 3단계 - 중첩된 for 루프에서 배열[m]이 배열[n]보다 큰지 확인합니다. 그렇다면 n+1번째 요소부터 마지막 ​​요소까지 반복합니다.

• 4단계 - 0번째 인덱스의 요소가 n번째 인덱스의 요소보다 작으면 크기 3의 유효한 역쌍을 찾았다고 말하고 'cnt' 변수에서 1을 뺀 값을 증가시킵니다.

• 5단계 - for 루프의 모든 반복이 완료된 후 "cnt" 값을 반환합니다.

예 1

아래 예에서는 크기 3의 반전 쌍의 총 개수를 찾기 위해 무차별 대입 방법을 구현합니다.

주어진 배열에서 사용자는 출력에서 ​​2개의 반전 쌍만 관찰할 수 있습니다. 첫 번째 반전 쌍은 (10,5,4)이고 두 번째 반전 쌍은 (20,5,4)입니다.

으아아아

시간과 공간의 복잡성

• Time Complexity - 세 개의 중첩된 for 루프를 사용하므로 시간 복잡도는 O(n^3)입니다.

• Space Complexity - 일정한 공간을 사용할 때 공간 복잡도는 O(1)입니다.

두 개의 중첩된 for 루프를 사용하세요

이 방법에서는 두 개의 중첩 루프를 사용합니다. 현재 요소의 오른쪽에 있는 작은 요소의 총 개수와 왼쪽에 있는 큰 요소의 총 개수를 찾습니다. 그런 다음 두 개를 곱하여 특정 숫자에 대한 총 반전 수를 얻습니다.

문법

사용자는 아래 구문에 따라 두 개의 중첩 루프를 사용하여 JavaScript에서 크기 3의 반전을 계산할 수 있습니다.

으아아아

알고리즘

• 1단계 - for 루프를 사용하여 배열의 n개 요소를 반복합니다.

• 2단계 - for 루프를 사용하여 현재 요소보다 작은 현재 요소 오른쪽에 있는 모든 요소를 ​​찾습니다.

• 3단계 - for 루프를 다시 사용하여 현재 요소보다 큰 현재 요소 왼쪽의 모든 요소를 ​​찾습니다.

• 4단계 - 왼쪽 변수와 오른쪽 변수의 값을 곱하여 "cnt" 변수에 추가합니다.

예 2

아래 예에서는 위 방법과 같이 두 개의 중첩 루프를 사용하여 크기 3의 총 반전 횟수를 찾습니다. 사용자는 출력이 첫 번째 방법과 동일하다는 것을 확인할 수 있습니다.

으아아아

시간과 공간의 복잡성

• Time Complexity - 두 개의 중첩 루프를 사용하므로 위 방법의 시간 복잡도는 O(n^2)입니다.

• Space Complexity - 일정한 공간을 사용할 때 공간 복잡도는 O(1)입니다.

사용자는 주어진 배열에서 크기 3의 반전 개수를 찾는 두 가지 방법을 배웠습니다. 첫 번째 접근 방식에서는 무차별 접근 방식을 사용하여 문제를 해결했으며, 두 번째 접근 방식에서는 시간 복잡성을 줄이기 위해 솔루션을 더욱 최적화했습니다.

위 내용은 주어진 배열에서 크기 3의 반전을 계산하는 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!