C 코드의 파이썬 변환이 작동하지 않습니다.

Question

분할 및 정복을 사용하여 O(log N) 시간의 배열에서 최대 요소를 찾고 싶습니다. planet-source-code에 작동 코드가 있습니다.

def largest(arr,i,j): 
    global max1 
    global max2 
    if i == j: 
     max1 = arr[i] 
    else: 
     if i == j-1: 
      max1 = arr[i] if arr[i] > arr[j] else arr[j] 
     else: 
       mid = (i+j)/2 
       largest(arr,i,mid) 
       max2 = max1 
       largest(arr,mid+1,j) 
       if max2 > max1: 
      max1 = max2 

을 내가 배열 [98,5,4,3,2,76,78,92]를 사용하고

max1 = arr[0] 
largest(arr,1,8) 

나는 아웃 - 오브 - 바운드리스트 인덱스 오류가 점점 오전으로 코드를 호출 할 때 다음과 같이 파이썬으로 번역. 그러나 C 코드는 올바른 결과 98을 리턴합니다.

Answer 1

일반적인 정렬되지 않은 배열의 경우 O (n) 시간보다 적은 시간에 max을 찾을 수 없습니다. 아주 간단한 증명 : 만약 당신이 O (n) 시간보다 적 으면, 충분히 큰 배열을 위해 모든 원소를 검사 할 시간이 없습니다. 따라서 상대방은 확인하지 않은 요소에 최대 값을 넣을 수 있으므로 알고리즘이 올바르지 않게됩니다. 원래 코드는 (할 것 순진한 구현으로) 2N보다 적은 수의 비교를 동시에 모두 최대 및 최소를 찾아 사용하는 좋은 무엇

는 - 그것은 단지 하나 개의 비교 때를 수행 이후 약 1.5N 비교를 사용하여이 두 요소입니다. 당신은 파이썬에서 max(arr)을 사용하는 것이 더 좋을 것입니다 (함수 호출 오버 헤드가 없으므로 더 빠름).

원래 코드는 a[1]에서 a[n]까지의 값을 저장하며 크기는 n+1입니다. 따라서 첫 번째 위치에 더미 요소를 넣어야합니다.

하지만 더 문제가 있으면 번역이 잘못되었습니다. 원본은 전역 값을 사용하여 다중 값 반환 (매우 위험한 방법) 및 이전 전역 변수를 저장하는 로컬 변수를 사용합니다. max1과 max2을 모두 전역으로 설정하기 때문에이 함수는 올바른 대답을 생성하지 못합니다. 당신은 동일한 코드를 사용하지 않는

def minmax(arr, i, j): 
    if i==j: 
     return arr[i], arr[i] 
    elif i==j-1: 
     if arr[i] < arr[j]: 
      return arr[i], arr[j] 
     else: 
      return arr[j], arr[i] 
    else: 
     mid = (i+j)//2 
     min1, max1 = minmax(arr, i, mid) 
     min2, max2 = minmax(arr, mid+1, j) 
     if min2 < min1: min1 = min2 
     if max2 > max1: max1 = max2 
     return min1, max1 

Answer 2

당신은 함수 호출을 가진 끝날 것

largest(arr, 7,8) 

그런 다음 코드

max1 = arr[i] if arr[i] > arr[j] else arr[j] 

인덱스 편곡을 시도합니다 [J] =의 편곡 [8] 파이썬으로, 경계 밖으로 가 1-8이 아닌 0-7의 벡터를 열거합니다.

나는 O (N)으로 이어지는 최대 요소를 찾기 위해 모든 요소를 ​​적어도 한 번 검사해야하기 때문에 O (log N) 알고리즘이 있다고 생각하지 않습니다.