algorithm - 리뷰 - 코딩 인터뷰 완전 분석 파이썬




쉬운 면접 질문은 더 열심히 얻었다:지정된 수 1..100,없는 수를 찾아 내십시오 (20)

2와 3 개의 누락 된 숫자 문제를 해결하기 위해 quickselect 를 수정할 수 있습니다. quickselect 는 평균적으로 O(n) 에서 실행되며 파티셔닝이 내부에서 완료되면 상수 메모리를 사용합니다.

  1. 피벗보다 작은 수를 포함하는 파티션 l 과 피벗보다 큰 수를 포함하는 r 으로 무작위 피벗 p 와 관련하여 집합을 분할합니다.

  2. 피벗 값을 각 파티션의 크기와 비교하여 누락 된 두 개의 숫자가있는 파티션을 결정합니다. ( p - 1 - count(l) = count of missing numbers in ln - count(r) - p = count of missing numbers in r )

  3. a) 각 파티션에 하나의 숫자가 누락 된 경우 누락 된 숫자를 찾기 위해 sums 방식의 차이를 사용하십시오.

    (1 + 2 + ... + (p-1)) - sum(l) = missing #1 ((p+1) + (p+2) ... + n) - sum(r) = missing #2 (1 + 2 + ... + (p-1)) - sum(l) = missing #1 ((p+1) + (p+2) ... + n) - sum(r) = missing #2

    b) 한 파티션에 두 숫자가 모두없고 파티션이 비어 있으면 누락 된 숫자는 숫자가 누락 된 파티션에 따라 (p-1,p-2) 또는 (p+1,p+2) 입니다.

    한 파티션에 2 개의 숫자가 누락되었지만 비어 있지 않은 경우 해당 파티션으로 재귀하십시오.

단 2 개의 누락 된 숫자로,이 알고리즘은 항상 적어도 하나의 파티션을 버리므로 quickselect의 O(n) 평균 시간 복잡성을 유지합니다. 마찬가지로 3 개의 누락 된 숫자로이 알고리즘은 각 패스마다 적어도 하나의 파티션을 삭제합니다. 2 개의 누락 된 숫자와 함께 최대 1 개의 파티션에 여러 개의 누락 된 숫자가 포함되기 때문입니다. 그러나 더 많은 누락 된 숫자가 추가 될 때 성능이 얼마나 떨어지는 지 잘 모르겠습니다.

다음은 현재 위치에서 파티션을 사용하지 않는 구현입니다.이 예제는 공간 요구 사항을 충족시키지 않지만 알고리즘의 단계를 보여줍니다.

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Demo

나는 재미있는 면접 경험을 가지고 있었다. 질문은 정말로 쉬워졌습니다.

Q1 : 숫자 1 , 2 , 3 , ..., 100 들어있는 가방이 있습니다. 각 숫자는 정확히 한 번 나타나므로 100 개의 숫자가 있습니다. 이제 하나의 번호가 무작위로 가방에서 선택됩니다. 누락 된 번호를 찾으십시오.

전에이 인터뷰 질문을 들었습니다. 그래서 나는 매우 빠르게 다음과 같은 답변을했습니다.

A1 : 숫자 1 + 2 + 3 + … + N(N+1)(N/2) ( Wikipedia : 산수 시리즈의 합계 참조). N = 100 인 경우 합계는 5050 입니다.

따라서 모든 숫자가 가방에 있으면 합계는 정확히 5050 입니다. 하나의 숫자가 누락되어 있기 때문에 그 합은 이보다 작을 것이며 그 차이는 그 숫자입니다. 따라서 O(N) 시간과 O(1) 공간에서 누락 된 수를 찾을 수 있습니다.

이 시점에서 나는 잘했다고 생각했지만 갑자기 질문에 예기치 않은 변화가 일어났습니다.

Q2 : 맞습니다.하지만 두 개의 숫자가 누락되면 어떻게 할 수 있습니까?

전에이 변형을 보거나 들었거나 고려하지 않았으므로 당황하여 질문에 답할 수 없었습니다. 면접관은 내 사고 과정을 알고 있다고 주장 했으므로 예상 제품과 비교하여 더 많은 정보를 얻거나 아마도 첫 번째 단계에서 일부 정보를 수집 한 후 두 번째 단계를 거쳐 더 많은 정보를 얻을 수 있다고 언급했지만 실제로는 어둠 속에서 실제로는 솔루션에 대한 명확한 경로가 있습니다.

면접관은 두 번째 방정식을 갖는 것이 실제로 문제를 해결하는 한 가지 방법이라고 말함으로써 나를 격려하려고했습니다. 이 시점에서 필자는 (손을 잡기 전에 답을 모르기 때문에) 화가났다. 그리고 이것이 일반적인 (읽기 : "유용한") 프로그래밍 기법인지, 아니면 단지 트릭 / 잡아라는 대답인지 물어 보았다.

인터뷰 담당자의 대답은 저를 놀라게했습니다. 기술을 일반화하여 누락 된 3 개의 숫자를 찾아 낼 수 있습니다. 사실, 그것을 누락 된 수를 찾기 위해 일반화 할 수 있습니다.

Qk : 정확히 k 개의 숫자가 가방에서 누락 된 경우 어떻게 효율적으로 찾을 수 있습니까?

몇 달 전 이었지만이 기법이 무엇인지 알 수 없었습니다. 우리가 적어도 한 번은 모든 수를 스캔해야하기 때문에 분명히 Ω(N) 시간 하한이 있지만 면접관은 해결 기법 ( O(N) 시간 입력 스캔 제외)의 TIMESPACE 복잡도가 k N 아닙니다.

여기서 질문은 간단합니다.

  • Q2를 어떻게 풀려고합니까?
  • Q3를 어떻게 풀려고합니까?
  • Qk를 어떻게 풀려고합니까?

설명

  • 일반적으로 1..100이 아니라 1 .. N의 N 개의 숫자가 있습니다.
  • 나는 명백한 세트 기반의 솔루션을 찾고 있지 않다. 예를 들어 비트 세트를 사용하여 각 비트를 지정된 비트의 값으로 존재 / 부존재를 인코딩하므로 추가 공간에서 O(N) 비트를 사용한다. 우리는 N에 비례하여 추가 공간을 감당할 수 없습니다.
  • 나는 또한 분명한 정렬 우선 접근법을 찾고 있지 않다. 이것과 집합 기반 접근법은 인터뷰에서 언급 할 가치가 있습니다 (구현하기 쉽고 N 에 따라 매우 실용적 일 수 있음). 성배 솔루션을 찾고 있는데 (실용적 일 수도 있고 그렇지 않을 수도 있지만 그럼에도 불구하고 바람직한 점근 특성이 있습니다).

따라서 물론 O(N) 에서 입력을 스캔해야하지만, ( k가 아닌 N의 관점에서 정의 된) 작은 양의 정보 만 캡처 할 수 있으므로 누락 된 수를 어떻게 든 찾아야합니다.


@j_random_hacker가 지적했듯이 이것은 O (n) 시간과 O (1) 공간에서 중복찾는 것과 매우 유사합니다.

"가방"이 크기 N - k 의 1- 기반 배열 A[] 로 표현된다고 가정하면 O(N) 시간의 Qk와 O(k) 추가 공간을 풀 수 있습니다.

먼저 배열 A[]k 요소만큼 확장하여 크기 N 이되도록합니다. 이것은 O(k) 추가 공간입니다. 그런 다음 다음과 같은 의사 코드 알고리즘을 실행합니다.

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

첫 번째 루프는 k 번째 추가 항목을 배열의 첫 번째 항목과 동일하게 초기화합니다 (이 단계는 배열에 이미있는 편리한 값입니다.이 단계 후에 크기의 초기 배열에서 누락 된 항목 Nk 는 여전히 확장 배열에서 누락되었습니다.)

두 번째 루프는 요소 x 가 적어도 한 번 존재하면 해당 항목 중 하나가 위치 A[x] 있도록 확장 배열을 대체합니다.

Nested 루프가 있지만 여전히 O(N) 시간에 실행됩니다. 스왑은 A[i] != i 와 같은 i 가있는 경우에만 발생하며 각 스왑은 A[i] == i , 전에는 사실이 아니 었습니다. 즉, 스왑의 총 수 (따라서 while 루프 본문의 총 실행 수)는 최대 N-1 입니다.

세 번째 루프는 값 i 차지하지 않는 배열 i 인덱스를 출력합니다. 이는 필자가 빠졌음을 의미합니다.


나는이 문제를 해결하기 위해 4 살짜리 아이에게 물었다. 그는 수를 분류하고 따라 계산했습니다. 이것은 O (주방 바닥)의 공간 요구 사항을 가지고 있으며, 많은 볼이 빠져있는 것처럼 쉽게 작동합니다.


모든 번호가 있는지 확인할 수 있습니까? 그렇다면 다음을 시도해보십시오 :

S = 백 내의 모든 숫자의 합 (S <5050)
Z = 누락 된 숫자의 합계 5050 - S

누락 된 숫자가 xy 이면 :

x = Z - y 및
max (x) = Z - 1

그래서 1 에서 max(x) 범위를 확인하고 숫자를 찾습니다.


영리한 트릭없이 바로 k 비트의 추가 스토리지를 사용하는 솔루션이 있습니다. 실행 시간 O (n), 추가 공간 O (k). 솔루션을 먼저 읽거나 천재가 아니더라도 이것이 해결 될 수 있음을 증명하기 위해 :

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= odd) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = even; i < n; ++i) data [i] += 1;
}

우리는 숫자 자체와 숫자의 제곱 을 합하여 Q2를 풀 수 있습니다.

그러면 문제를 다음과 같이 줄일 수 있습니다.

k1 + k2 = x
k1^2 + k2^2 = y

여기서 xy 는 합계가 기대 값보다 얼마나 떨어지는 지입니다.

대체하면 우리에게 준다 :

(x-k2)^2 + k2^2 = y

우리는 다음 누락 된 숫자를 결정하기 위해 해결할 수 있습니다.


확실하지 않은 경우 가장 효율적인 솔루션이지만 모든 항목을 반복하고 비트 세트를 사용하여 기억할 숫자를 설정 한 다음 0 비트를 테스트합니다.

나는 단순한 해법을 좋아한다. 그리고 나는 심지어 합이나 합계를 계산하는 것보다 빠르다는 것을 믿는다.


1에서 50까지의 숫자의 제품을 찾으십시오.

곱을 P1 = 1 x 2 x 3 x ............. 50이라고하자.

숫자를 하나씩 꺼내면 곱 해져 제품 P2가됩니다. 그러나 여기에는 두 개의 숫자가 없으므로 P2 <P1입니다.

두 개의 mising term의 결과, axb = P1 - P2.

당신은 이미 a + b = S1을 알고 있습니다.

위의 두 방정식으로부터 2 차 방정식을 통해 a와 b를 구하십시오. a와 b는 누락 된 숫자입니다.


link 페이지의 두 페이지를 읽어 보면 알 수 있습니다. 그것은 당신이 찾고있는 일반화를 정확하게 보여줍니다 . 아마도 이것은 당신의 면접자가 읽었던 것이고 왜 그가이 질문을 제기했는지입니다.

이제 사람들 만이 Muthukrishnan의 치료에 포함되거나 대체 된 답변을 삭제하기 시작하고이 텍스트를 찾기 쉽습니다. :)

또한 sdcvvc's 직접 관련 답변을 참조하십시오. sdcvvc's 에는 의사 코드 (hurray! 그 까다로운 수학 공식을 읽을 필요가 없습니다 :)) (감사합니다, 훌륭한 일!)도 포함됩니다.


Q2의 경우 이것은 다른 것보다 조금 비효율적이지만 O (N) 런타임을 가지고 O (k) 공간을 사용하는 솔루션입니다.

아이디어는 원래 알고리즘을 두 번 실행하는 것입니다. 처음에는 누락 된 총 수를 얻습니다. 누락 된 수의 상한선을 제공합니다. 이 번호로 전화를 걸자 N. 당신은 누락 된 두 숫자가 정리해가는 것을 알고 N첫 번째 숫자는 간격에있을 수 있도록, [1, floor((N-1)/2)]두 번째가 될 것입니다 동안 [floor(N/2)+1,N-1].

따라서 첫 번째 간격에 포함되지 않은 모든 숫자를 버리고 모든 숫자를 다시 한 번 반복합니다. 그것들은 합계를 추적합니다. 마지막으로 누락 된 두 숫자 중 하나를 알 수 있고, 두 번째 숫자는 연장으로 알 수 있습니다.

나는이 방법이 일반화 될 수 있고 입력에 대한 단일 패스 중에 여러 검색이 "병렬"로 실행될 수 있다고 생각하지만 아직 방법을 찾지 못했습니다.


두 목록과 두 목록의 합이 있으면 Q2를 풀 수 있습니다.

(l1은 원본이고 l2는 수정 된 목록입니다)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

산술 계열의 합계가 처음과 마지막 용어의 평균 n 배가되기 때문에이를 최적화 할 수 있습니다.

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

이제 우리는 그것을 알고 있습니다 (a와 b가 제거 된 숫자 인 경우).

a + b = d
a * b = m

그래서 우리는 재정렬 할 수 있습니다 :

a = s - b
b * (s - b) = m

그리고 곱하면된다.

-b^2 + s*b = m

오른쪽면이 0이되도록 재정렬하십시오.

-b^2 + s*b - m = 0

그런 다음 이차 공식으로 풀 수 있습니다.

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Python 3 코드 샘플 :

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

sqrt, reduce 및 sum 함수의 복잡성을 알지 못하므로이 솔루션의 복잡성을 해결할 수 없습니다 (누군가가 아래에 의견을 말하면 알고있는 경우).


또 다른 방법은 잔여 그래프 필터링을 사용하는 것입니다.

1에서 4까지의 숫자가 있고 3이 없다고 가정 해보십시오. 이진 표현은 다음과 같다.

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

그리고 다음과 같은 흐름 그래프를 만들 수 있습니다.

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

흐름 그래프는 x 노드를 포함하고 x는 비트 수를 포함합니다. 그리고 최대 모서리 수는 (2 * x) -2입니다.

따라서 32 비트 정수의 경우 O (32) 공간 또는 O (1) 공간이 필요합니다.

이제 1,2,4에서 시작하여 각 숫자에 대한 용량을 제거하면 잔여 그래프가 남습니다.

0 ----------> 1 ---------> 1

마지막으로 다음과 같은 루프를 실행합니다.

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

이제 결과 result에는 누락되지 않은 숫자도 포함됩니다 (거짓 긍정). 그러나 누락 된 요소 가있을 때 k <= (결과의 크기) <= nk 입니다.

마지막으로 누락 된 결과를 표시하기 위해 주어진 목록을 살펴 보겠습니다.

그래서 시간의 복잡성은 O (n)가 될 것입니다.

마지막으로, 거짓 양성 (및 필요한 공간) 복용 노드에서의 수를 줄일 수있다 00, 01, 11, 10대신 단지 01.


아이디어가 있지만 배열의 실제 크기가 100이고 누락 된 숫자가 -1과 같은 다른 것으로 대체된다고 가정합니다.

기본적으로, 목록을 내부 교체하는 선택 정렬의 수정 된 버전 일종의 정렬을 수행하십시오. 나는 우리가 이미 존재해야하는 숫자를 알고 있다는 사실을 이용하기 때문에 이것이 O (n) 시간이라고 믿는다. 우리는 인덱스가 올바른 숫자 (또는 -1)를 가질 때까지 값을 "올바른"위치로 바꿉니다.

그 작업을 마친 후에는 목록을 다시 반복하면 인덱스는 기본적으로 누락 된 숫자가됩니다.

#Set up the input
input = (1..100).to_a.shuffle
input[rand(0..99)] = -1
input[rand(0..99)] = -1

def f(a)
  for i in 0..99
    while (a[i] != i+1) && a[i] > 0
      v1 = a[i]
      v2 = a[v1 - 1]
      a[i] = v2
      a[v1 - 1] = v1
    end
  end

  result = []
  a.each_with_index do |value, index|
    if value < 0
      result.push(index + 1)
    end
  end

  return result
end

#Returns the 2 missing numbers
puts f(input)

이 알고리즘은 질문 1에서 작동 할 수 있습니다.

  1. 처음 100 개의 정수를 미리 계산하십시오 (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
  2. 요소들이 입력 스트림 (val1 = val1 ^ next_input)에서 계속 나오면서 요소를 xor
  3. 최종 답 = val ^ val1

또는 더 나은 :

def GetValue(A)
    for i=1 to 100
     do
       val=val^i
     done
     for value in A:
       do
         val=val^value 
       done
    return val

이 알고리즘은 실제로 두 개의 누락 된 숫자에 대해 확장 될 수 있습니다. 첫 번째 단계는 동일하게 유지됩니다. 두 개의 누락 된 숫자로 GetValue를 호출하면 결과는 a1^a2누락 된 두 개의 숫자가됩니다. 의 말을하자

val = a1^a2

이제 val에서 a1과 a2를 체로 치기 위해 우리는 val에서 임의의 세트 비트를 취합니다. 말할 수 있습니다 ith비트가 발에 설정되어 있습니다. 이는 a1과 a2가 ith비트 위치 에서 다른 패리티를 가짐을 의미합니다 . 이제 원래 배열에서 또 다른 반복을 수행하고 두 xor 값을 유지합니다. 하나는 i 번째 비트가 설정되고 다른 하나는 i 번째 비트가 설정되지 않은 숫자입니다. 우리는 이제 두 개의 양동이를 가지고 a1 and a2있으며, 다른 양동이에 누워있는 양심의 가책을 가지고 있습니다. 이제 각 양동이에 하나의 누락 된 요소를 찾기 위해 수행했던 작업을 반복합니다.


이것이 효율적인 지 아닌지는 모르겠지만이 해결책을 제안하고 싶습니다.

  1. 100 개 요소의 xor를 계산합니다.
  2. 98 개 요소의 xor를 계산합니다 (2 개 요소가 제거 된 후).
  3. 지금 (1의 결과) XOR (결과 2)는 두 개의 누락 된 노드의 xor를 제공합니다 .e..ea XOR b a와 b가 누락 된 요소 인 경우
    4. 누락 된 Nos의 합계를 합계 수식 diff를 사용하면 diff가 d라고 할 수 있습니다.

이제 루프를 실행하여 가능한 쌍 (p, q)을 모두 [1, 100]에 놓고 d에 합을 얻으십시오.

쌍이 얻어지면 (3의 결과) XOR p = q를 확인하고, 맞으면 우리는 완료됩니다.

내가 틀렸다면 나에게 정정하고 시간 복잡성에 대해서도 의견을 말하십시오.


블룸 필터를 사용해 볼 수도 있습니다. 가방에있는 각 번호를 블룸에 넣은 다음, 각 1-k 세트가 발견되지 않을 때까지 반복합니다. 이것은 모든 시나리오에서 답을 찾을 수는 없지만 충분한 해결책이 될 수 있습니다.


나는 이것이 복잡한 수학 방정식과 이론 없이도 가능하다고 생각한다. 다음은 제자리 및 O (2n) 시간 복잡성 솔루션에 대한 제안입니다.

입력 폼 가정 :

bag에있는 숫자의 수 = n

누락 된 숫자의 수 = k

가방 안의 숫자는 길이가 n 인 배열로 표현됩니다.

algo = n에 대한 입력 배열의 길이

배열의 누락 된 항목 (가방에서 가져온 숫자)은 배열의 첫 번째 요소 값으로 대체됩니다.

예 :처음에 가방은 [2,9,3,7,8,6,4,5,1,10]와 같이 보입니다. 4가 꺼내지면 4의 값은 2 (배열의 첫 번째 요소)가됩니다. 따라서 4를 꺼내면 가방은 [2,9,3,7,8,6,2,5,1,10]

이 솔루션의 핵심은 배열이 순회 될 때 해당 INDEX의 값을 무효로하여 방문한 번호의 INDEX에 태그를 지정하는 것입니다.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

대칭 (그룹, 수학 언어) 측면에서 솔루션을 생각함으로써 동기를 부여 할 수 있습니다. 숫자 집합의 순서와 관계없이 답은 동일해야합니다. k누락 된 요소를 결정하는 데 도움이되는 함수 를 사용하려면 함수에 해당 함수가 있는지 생각해야합니다 : 대칭 함수. 이 함수 s_1(x) = x_1 + x_2 + ... + x_n는 대칭 함수의 예이지만 더 높은 차수의 함수가 있습니다. 특히 기본 대칭 함수를 고려하십시오 . 차수 2의 기본 대칭 함수 s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n는 두 요소의 모든 곱의 합입니다. 차수 3 이상의 기본 대칭 함수에 대해서도 마찬가지입니다. 그들은 분명히 대칭입니다. 또한 모든 대칭 함수의 기초가되는 것으로 밝혀졌습니다.

당신은 그것을 지적함으로써 기본 대칭 함수를 만들 수 있습니다 s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). 추가 생각은 당신을 s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))그렇게 확신시켜야합니다 . 그래서 그들은 한 번에 계산할 수 있습니다.

배열에서 누락 된 항목을 어떻게 알 수 있습니까? 다항식에 대해 생각해보십시오 (z-x_1)(z-x_2)...(z-x_n). 그것은 0당신이 숫자 중 하나를 입력하면 평가 합니다 x_i. 다항식을 확장하면 얻을 수 z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n있습니다. 초등 대칭 함수도 여기에 표시됩니다. 실제로 어떤 놀람도 없습니다. 왜냐하면 우리가 뿌리에 순열을 적용하면 다항식이 동일하게 유지되어야하기 때문입니다.

그래서 우리는 다항식을 만들 수 있고 다른 숫자가 언급했듯이 어떤 숫자가 집합에 들어 있지 않은지 알아 내기 위해 그것을 다듬을 수 있습니다.

우리는 많은 수의 메모리를 오버 플로우에 대해 우려하는 경우 마지막으로, (n 번째 대칭 다항식은 주문이 될 것입니다 100!, 우리는 이러한 계산을 할 수있는) 우리가 다항식을 평가하는 경우 (100)보다 주요 크다 과 다시 평가하는 것을 발견을 에 대한 입력은 일련의 숫자이며, 입력 번호가 설정되지 않을 때 그것이 0이 아닌 값으로 평가할 때. 다른 사람들이 지적 그러나,에 따라 시간에 다항식에서 값을 얻기 위해 ,하지 , 우리는 다항식을 인수 분해해야한다 .mod ppmod p0kNmod p


우리는 대부분의 시간 에 O (log n) 에서 Q1과 Q2 를 할 수 있습니다 .

우리 memory chipn수의 배열로 구성 된다고 가정하십시오 test tubes. 그리고 x테스트 튜브 의 숫자 x milliliter는 화학 - 액체로 표시됩니다 .

우리의 프로세서가 laser light. 우리가 레이저를 밝힐 때 모든 튜브를 그 길이에 수직으로 가로 지릅니다. 약액을 통과 할 때마다 광도가 감소합니다 1. 그리고 특정 밀리리터 마크에서 빛을 통과시키는 것은 작업입니다 O(1).

이제 우리가 테스트 튜브의 중간에서 레이저를 비추고 광도의 출력을 얻으면

  • (누락 된 숫자가없는 경우 계산 된) 사전 계산 된 값과 같으면 누락 된 숫자가보다 큽니다 n/2.
  • 우리의 산출물이 더 작 으면, 적어도 하나는 누락 된 수보다 적습니다 n/2. 또한 광도가 1또는 로 감소되었는지 확인할 수 있습니다 2. 이 감소되는 경우 1다음 누락 한 개수보다 작은 n/2다른보다 크다 n/2. 그것이 2그때까지 감소되는 경우에 두 수는보다는 더 작다 n/2.

위의 과정을 반복하여 문제 영역을 다시 좁힐 수 있습니다. 각 단계에서 도메인을 절반으로 줄입니다. 그리고 마침내 우리는 우리의 결과에 도달 할 수 있습니다.

언급 할만한 가치가있는 병렬 알고리즘 (흥미 롭기 때문에)

  • 예를 들어 병렬 병합과 같은 병렬 알고리즘을 시간순으로 정렬 할 수 있습니다 O(log^3 n). 그리고 나서 누락 된 수는 2 진 검색을 통해 찾아 낼 수 있습니다 O(log n).
  • 이론적으로 우리가 n프로세서를 가지고 있다면 각 프로세스는 입력 중 하나를 체크하고 그 수를 식별하는 플래그를 설정할 수있다. 그리고 다음 단계에서 각 프로세스는 각 플래그를 검사하고 플래그가 지정되지 않은 번호를 출력 할 수 있습니다. 전체 과정에 O(1)시간 이 걸릴 것입니다. 추가 O(n)공간 / 메모리 요구 사항이 있습니다.

것을 유의 주석에서 설명한 바와 같이 상기 제공된 두 개의 병렬 알고리즘의 추가 공간을 필요로 할 수있다 .


이와 같은 스트리밍 알고리즘을 일반화하는 일반적인 방법이 있습니다. 아이디어는 k우리의 원래 알고리즘이 우리에게 문제를 해결하는 독립적 인 하위 문제로 요소를 '확산'하기 위해 약간의 무작위 화를 사용하는 것입니다. 이 기술은 다른 것들 중에서 스파 스 신호 재구성에 사용됩니다.

  • a크기 의 배열을 만드십시오 u = k^2.
  • 어떤 선택 보편적 인 해시 함수를 , h : {1,...,n} -> {1,...,u}. ( multiply-shift 와 유사 )
  • 증가하는 각자 i1, ..., n위해a[h(i)] += i
  • x입력 스트림의 각 숫자 에 대해 감소 a[h(x)] -= x합니다.

누락 된 숫자가 다른 버킷으로 해시 된 경우 배열의 0이 아닌 요소에 누락 된 숫자가 포함됩니다.

특정 쌍이 동일한 버킷으로 전송 될 확률 1/u은 보편적 인 해시 함수의 정의 보다 적습니다 . k^2/2쌍 에 대한 것이 있기 때문에 , 오류 확률은 최대 k^2/2/u=1/2입니다. 즉, 우리는 확률이 50 % 이상으로 성공하며, 증가하면 u확률이 높아집니다.

이 알고리즘은 k^2 logn공간 비트를 필요로합니다 (우리 logn는 배열 버킷 당 비트 가 필요합니다 .) 이것은 @Dimitris Andreou의 대답 (특히 무작위 화되는 다항식 인수 분해의 공간 요구 사항)에 필요한 공간과 일치합니다.이 알고리즘은 또한 상수 k전력 합계의 경우 시간보다는 업데이트 당 시간 .

사실, 우리는 의견에 설명 된 트릭을 사용하여 전력 합계 방법보다 훨씬 더 효율적일 수 있습니다.





math