범위 LCM 쿼리를 위한 JavaScript 프로그램

王林
풀어 주다: 2023-09-02 19:17:11
앞으로
858명이 탐색했습니다.

用于范围 LCM 查询的 JavaScript 程序

LCM은 최소 공배수를 나타내며, 숫자 집합의 LCM은 주어진 집합에 존재하는 모든 숫자로 나누어지는 모든 숫자 중에서 가장 작은 숫자입니다. 주어진 문제에 대한 설명과 함께 전체 코드를 살펴보겠습니다. 이 기사에서는 일련의 LCM 쿼리에 대한 JavaScript 프로그램을 구현합니다.

문제 소개

이 문제에서는 정수를 포함하는 배열과 주어진 배열 범위를 나타내는 숫자 쌍을 포함하는 또 다른 배열 쿼리가 제공되며 해당 범위에 있는 모든 요소의 LCM을 계산해야 합니다. 예를 들어 -

주어진 배열이 [1, 2, 3, 4, 5, 6]이고 쿼리 배열이 [[1,3], [2,5]]인 경우 첫 번째 쿼리 요소는 [2, 3 , 4] 및 12는 LCM입니다.

두 번째 쿼리 요소가 [3, 4, 5, 6]인 경우 LCM은 60입니다.

LCM과 GCD의 수학적 관계

GCD를 찾기 위해 우리는 로그 복잡도의 두 숫자의 GCD를 찾을 수 있는 유클리드 공식을 가지고 있으며 LCM과 GCD 사이에는 이러한 관계가 있습니다. -

으아악

그래서 우리는 모든 숫자의 GCD와 곱을 찾은 다음 거기에서 O(1) 연산을 통해 해당 숫자의 LCM을 찾을 수 있습니다.

순진한 방법

가장 쉬운 방법은 쿼리 배열을 반복하고 주어진 범위의 요소와 각 쿼리의 GCD의 곱을 찾는 것입니다. 이 두 값에서 LCM을 찾아 반환합니다. 코드로 구현해보자 -

으아악

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(Q*N*log(D))입니다. 여기서 Q는 쿼리 수, N은 배열의 요소 수, D는 쿼리에 존재하는 최대 배열 수입니다. 정렬.

위 코드의 공간 복잡도는 추가 공간을 사용하지 않기 때문에 O(1)입니다.

위 프로그램에서 쿼리 수가 N과 같으면 시간 복잡도가 N2보다 커지므로 이 방법이 비효율적입니다. 이것이 또 다른 방법인지 살펴보겠습니다 &miinus;

선분 트리 방법

세그먼트 트리는 문제를 여러 세그먼트로 나눈 다음 이를 2의 거듭제곱으로 연결하는 데 사용되는 상위 수준 데이터 구조입니다. 이를 위해서는 범위 쿼리를 위한 약간의 공간이 필요하며 로그 시간에 결과를 생성합니다. 코드를 살펴보겠습니다 -

으아악

결론

이 튜토리얼에서는 범위 lcm 쿼리를 찾기 위한 JavaScript 기사를 구현했습니다. 우리는 두 가지 방법을 보았습니다. 하나는 시간 복잡도가 O(Q*N*log(D))인 순진한 방법이고, 다른 하나는 시간 복잡도가 O(Q*log(N))인 선분 트리입니다. p>

위 내용은 범위 LCM 쿼리를 위한 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:tutorialspoint.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿