N의 K번째 인자 - O(sqrt n) 알고리즘

소개

최근에 저는 Big O 표기법을 한번에 배워보세요라는 글을 썼습니다. 해당 게시물에서는 Big-O 치트시트에서 사용할 수 있는 모든 유형의 Big O 시간 표기법을 살펴봅니다. 그리고 나는 그 7개 외에 더 이상 시간 표기가 가능하다고 생각하지 않았습니다.

우주 그 자체가 나를 낮추고 나의 무지함을 조롱하듯, O(√n)시간의 해결로 LeetCode 문제를 접하게 되었습니다. 미쳤다면 O(N^1/2)로 번역할 수 있습니다.

문제

두 개의 양의 정수 n과 k가 주어졌습니다. 정수 n의 인수는 n % i == 0인 정수 i로 정의됩니다.

오름차순으로 정렬된 n의 모든 요소 목록을 고려하고, 이 목록에서 k번째 요소를 반환하거나 n의 요소가 k보다 작으면 -1을 반환합니다.

확실한 해결책

글쎄, 당신이 나와 같다면 가장 먼저 생각한 것은 1부터 n까지의 모든 숫자를 살펴보고 그것이 인수인지 확인한 다음 원하는 k 인덱스에 있으면 반환하는 것이었습니다.

코드는 다음과 같습니다.

def getkthFactorOfN(n, k):
    result = 0
    for i in range(1, n + 1):
        if n % i == 0:
            result = result + 1
            if result == k:
                return i
    return -1

이거 다 괜찮고 멋있지만 "오직" O(n)이에요. 결국 루프는 하나뿐이고 n 1까지 올라갑니다.
시간 표기를 고려하면 다른 모든 작업은 무시됩니다.

하지만 친구여, 문제가 있어요.

요인 이해

생각해보면 특정 시점 이후에는 요소가 '미러링'됩니다.

예를 들어 숫자 81을 생각해 보세요. 인수는 [1, 3, 9, 27]입니다.

• 1 * 81 = 81
• 3 * 27 = 81
• 9 * 9 = 81
• 27 * 3 = 81
• 81 * 1 = 81

숫자 9를 세지 않으면 단순히 연산이 반복되고 뒤집어집니다. n을 해당 인수 중 하나로 나누면 또 다른 인수가 나옵니다.
n의 제곱근은 제곱이 됩니다(duh).

이 지식을 바탕으로 이제 우리는 루프를 최대 n회(range(1, n 1) 사용)까지 반복할 필요가 없고 단지 math.sqrt(n)까지 반복할 필요가 있다는 것을 알게 되었습니다. 그러면 필요한 모든 요소가 확보됩니다!

그다지 명확하지 않은 해결책

이제 필요한 모든 것이 준비되었으므로 이 루프를 1 -> n에서 1로 -> sqrt n.

여기에 코드를 입력하고 한 줄씩 살펴보겠습니다.

def getkthFactorOfN(n, k):
    i = 1
    factors_asc = []
    factors_desc = []
    while i * i <= n:
        if n % i == 0:
            factors_asc.append(i)
            if i != n // i:
                factors_desc.append(n // i)
        i += 1
    if k <= len(factors_asc):
        return factors_asc[k-1]
    k -= len(factors_asc)
    if k <= len(factors_desc):
        return factors_desc[-k]
    return -1

아, 훨씬 더 복잡하네요. 분석해 보겠습니다.

먼저 i = 1로 초기화합니다. 이 변수는 요인 검색 시 "현재 위치"로 사용됩니다.

두 번째로, Factor_asc와 Factor_desc라는 두 개의 배열을 만듭니다. 여기서 마술은 Factor_asc에 요인을 추가한다는 것입니다. 요인은 자동으로 오름차순으로 정렬되기 때문에 이렇게 이름이 지정되었습니다.
Factors_asc에 무엇인가를 추가할 때마다 n을 이것으로 나누어 Factor_desc에 추가합니다. 여기에도 비슷한 논리가 있습니다. 편리하게 내림차순으로 추가됩니다.

그런 다음 루프를 시작합니다. 여기서는 n의 루트에 도달하면 중지하므로 while i * i <= n으로 변경했습니다.

현재 숫자가 인수(n % i == 0)인지 확인하는 것부터 시작합니다. 그렇다면 이를 Factor_asc 배열에 추가할 수 있습니다.

다음으로 i의 "역인수"를 구합니다. i != n // i, 즉 루트가 아닌지 확인하여 이를 수행할 수 있습니다. 이는 두 배열 모두에서 루트가 중복되어서는 안 되기 때문입니다. 그렇지 않은 경우 n // i를 실행하고 그 결과를 Factor_desc에 추가하여 반전된 인수를 얻습니다.

이후 i에 1을 더하고 루프를 계속합니다.

루프가 완료된 후에는 필요한 모든 계승이 있어야 합니다.

if k

그렇지 않다면 k에서 찾은 요소의 양을 빼고 k -= len(factors_asc) 및 k

k가 Factor_desc 내부에 있는 경우 Factor_desk[-k]를 사용하여 해당 값을 가져옵니다(마지막에서 처음으로).

모두 실패하면 -1을 반환합니다.

곡선

곡선 그래프에서 그것이 어디에 있는지 궁금하다면 O(n)과 O(log n) 사이에 있을 것입니다. 전자보다 좋고 나쁨입니다. 후자보다. 그래프는 다음과 같습니다.

Mathspace에서 사용 가능

결론

이것은 발견하고 조사하는 여행이었습니다. 여기까지 읽어주셔서 정말 감사드립니다.

좀 더 최적화하려면 Factor_asc_len 및 Factor_desc_len 변수를 생성하고 이러한 배열에 값을 추가할 때마다 1을 추가하면 됩니다. 그러면 len() 메소드를 호출할 필요가 없습니다. O(n) 시간 표기에 영향을 미칠 수 있습니다.

다음 공부까지 행운을 빕니다!

위 내용은 N의 K번째 인자 - O(sqrt n) 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!