그래서 나는 다음 문제를하고 있었다 : https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
더 최적의 이진 검색 솔루션이 있다는 것을 알고 있지만 처음에는 재귀 솔루션을 생각했고 시간 복잡성을 설명하는 가장 쉬운 방법에 대해 확신하지 못했습니다.
기본적으로 내 무차별 대입 접근 방식은 어레이에 대해 길이 D의 모든 접두사를 통과 한 다음 (각각은 1 일에 배송 할 수있는 잠재적 패키지를 나타냄), 각 접두사에 대해 나머지 접두사에 대해 반복하는 것입니다. D-1 일로 나머지 패키지를 배송 할 수있는 최소 용량을 파악하기 위해 감소 된 값 D를 가진 어레이. 그런 다음 hte 접두사와 재귀 결과의 합의 최대 값은 해당 접두사에 해당하는 최소 용량을 제공합니다.
그런 다음 기본적으로 모든 접두사에 대해이 작업을 수행하고 모든 접두사에서 최소 용량을 얻어야합니다. 코드는 다음과 같습니다. 인터뷰에서 시간 복잡성을 어떻게 쉽게 유도하는지 모르겠습니다. (여기에 버그가있을 수 있습니다. 개념을 설명하기 위해이 코드를 빠르게 적어 두었습니다.)
def shipWithinDays(weights, D):
if D == 1:
return sum(D)
min_capacity = float('inf')
capacity_till_i = 0
for i in xrange(D):
capacity_till_i += weights[i]
capacity_for_remaining = shipWithinDays(weights[i+1:],D-1)
min_capacity = min(min_capacity, max(capacity_till_i, capacity_for_remaining))
return min_capacity
이제 대부분의 algo 클래스에서 배운 "Unrolling method"를 사용하여이를 분석 할 수 있다는 것을 알고 있습니다. 따라서 시간 복잡도가 T (n)이면 제 경우에는 첫 번째 재귀 호출 후 재귀가 길이 n의 배열을 처리합니다. 1, n-2 등을 배열 길이 n-D로 설정합니다. 이렇게하면 다음과 같은 반복 관계가 생성됩니다.
T (n) = T (n-1) + T (n-2) + T (n-3) + ... + T (nD)
이제 T (n-1) 항을 풀면 다음과 같은 T (n-1) = T (n-2) + T (n-3) + .... + T (n -1-D)
T (n) = 2T (n-1) + T (n-1-D) ^ 위의 내용이 2 ^ n 또는 다른 것으로 단순화되어야한다고 생각합니다. 특히 인터뷰 환경에서하기에는 수학이 너무 무거워요. 왜 2 ^ n인지 설명하는 더 직관적 인 방법이 있나요?
왜 2 ^ n인지 설명하는 더 직관적 인 방법이 있습니까?
우선 2^n. 그것은 실제로 지수 적이며 n 제곱의 어떤 것이지만 이것이 반드시 2는 아닙니다.
약간의 수학 : 모든 선형 반복 관계는 다음과 같은 형태의 해를 허용합니다 T(n) = a ** n. 여기서는 a특성 다항식의 근입니다.
a ** D = a ** {D-1} + a ** {D-2} + ... + 1
이제 증명해야 할 것은 1보다 큰 뿌리가 있다는 것입니다. 이것은 다소 사소한 것입니다. 실제로 a1과 같으면 왼쪽 (1)이 오른쪽 ()보다 작습니다 D. a무한대 로 성장함에 따라 LHS는 RHS보다 빠르게 성장하고 결국 더 커집니다. 그것은 a > 1그들이 동등한 존재가 있음을 의미합니다 .
이것은 거의 다입니다. 내면의 수학 선생님이 좀 더 듣고 싶어합니다. 면접관으로서 나는 매우 만족할 것입니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다