O (1) 공간과 O (n)을 포함하는 시간

Question

내가 leetcode의 문제를 해결하고 있습니다

각 정수는 1과 N 사이에 여기서 n + 1의 정수를 포함

을 감안할 때 배열 nums (와 중복 번호를 찾을 수), 적어도 하나의 중복 된 숫자가 존재해야 함을 증명하십시오. (1, 단 하나의 중복 된 숫자가 있다고 가정 내가 솔루션 허용 얻었다 O (n)이 시간과 O (1) 공간의 복잡성

class Solution(object): 
    def findDuplicate(self, nums): 
     """ 
     :type nums: List[int] 
     :rtype: int 
     """ 
     xor=0 
     for num in nums: 
      newx=xor^(2**num) 
      if newx<xor: 
       return num 
      else: 
       xor=newx 

의 중복을 찾을 나는 둘 다 O이라고 들었습니다) 공간 또는 O (n) 시간.

아무도 도와 주실 수 없습니까?

Answer 1

해결책은 O (1) 공간이 아닙니다. 즉, 공간/메모리가 상수가 아니지만 입력에 따라 다릅니다. num가 log_2(2**num) = num 비트 결과의 결과, 사용자의 입력 번호 중 하나이고

newx=xor^(2**num) 

이

는 log_2(2**num) = num 비트 이상의 비트 단위 XOR된다.

so n=10 = log_2(2^10) = 10 bits, n=100 = log_2(2^100) = 100 bits. 선형 적으로 커지고 있습니다 (일정하지 않습니다).

그것의도하지 O 내에서 (n)의 시간 복잡도 당신이있어 같이

• 모든 N 번호를 통해 외부 루프
  • 및 비 일정/비 O (1) inner- 루프
  • 가정 (상기 참조)는 XOR
    • 항상 취급하지있어 그 입력의 비트 표현에 관해서 일정하지이고; 하지만 물리학은

Answer 2

귀하의 질문에 대한 답변을 실제로 어렵다 (... 찬드라 세 카르 한계, 빛의 속도)이 주장을 뒷받침. 일반적으로 복잡성을 다룰 때, 가정 된 기계 모델이 있습니다. A standard model은 입력이 크기 n 인 경우 메모리 위치가 크기 log (n) 비트이고 크기 log (n) 비트 수에 대한 산술 연산이 O (1)라고 가정합니다.

이 모델에서 코드는 공간의 O (1) 시간대의 O (n)이 아닙니다. 귀하의 xor 값은 n 비트를 가지고 있으며 이것은 상수 메모리 위치에 맞지 않습니다 (실제로 n/log (n) 메모리 위치가 필요합니다). 마찬가지로 산술 연산이 더 큰 숫자에 있기 때문에 시간 상 O (n)이 아닙니다. log (n) 비트보다

O (1) 공간과 O (n) 시간의 문제를 해결하려면 값이 너무 커지지 않도록해야합니다. 하여 배열의 숫자 및 d는 따라서 당신은 배열의 총 XOR에서 1^2^3^..^n을에 xor하고, 중복 된 값을 찾을 수 있습니다. 중복입니다 다음 1^2^3...^n^d를 얻을 수 있습니다.

def find_duplicate(ns): 
    r = 0 
    for i, n in enumerate(ns): 
     r ^= i^n 
    return r 

print find_duplicate([1, 3, 2, 4, 5, 4, 6]) 

이 O는 (1) 공간, 0 (O) 시간 이후의 O (n) 시간은 n보다 많은 비트를 사용하지 않습니다 (즉, 약 ln (n) 비트).