을 구현하는 경우 CompareToAll 메서드를 사용하여 배열에서 최대 수를 얻습니다. 각 숫자를 다른 숫자와 비교하지 않고 각 숫자를 그 이후에 나오는 숫자 만 비교하는 기능을 향상시킵니다. 본질적으로, 현재 숫자 이전의 모든 숫자는 이미 현재 숫자와 비교되었습니다. 따라서 현재 숫자 이후에 나오는 숫자와 비교할 때 알고리즘은 여전히 정확합니다. 이제 왜이 최악의 경우 실행 시간이 O (n2) O ("n square")인지 이해할 수 있습니다. 하지만 내가 이해할 수없는 것은 가능한 가장 빠른 실행 시간이 O (1) 인 이유입니다. 나는 그것이 최상의 경우에 있어야합니다 생각CompareToAll의 가장 빠른 실행 시간이 O (1) 인 이유는 무엇입니까?
는 O (N)에 동일 당신이 적어도 한 번 각 숫자를보고 있기 때문에 Big-O analysis for best case is copied from
Max() 기능에 대한 최소 복잡성, O(n)하지 O(1)입니다.
각 숫자를 한 번만 이전의 최대 수치와 비교하면됩니다. 이것은 파이썬에서 코드입니다 :
def max(a):
assert len(a) > 0
current = a[0]
for x in a[1:]:
if x > current: current = x
return current
정렬 된 배열의 경우, 가장 빠른 시간은 O (1) 당신이 정렬 방향에 따라, 단순히 첫 번째 또는 마지막 요소를 선택할 수 있기 때문이다. 그러나 정렬되지 않은 배열의 경우 O (n)보다 적은 시간에 max를 찾을 수있는 알고리즘을 예측할 수 없습니다.
이유 : 알려진 순서가 아닌 n 개의 요소가있는 배열이 있다고 가정합니다. 첫 번째 요소를 선택하십시오. 잠재적으로 이것은 최대 값입니다. 그러나 두 번째 요소가 최대 값이 아닌지 어떻게 알 수 있습니까? 테스트 해봐야 할 것입니다. 마찬가지로 세 번째 요소가 최대 값이 아니라는 것을 어떻게 알 수 있습니까? 그 밖에도 n 개의 테스트가 있습니다.