[theory] O (1 / n) 알고리즘이 있습니까?

이 질문은 생각보다 어리석지 않습니다. 이론적으로, O (1 / n ) 과 같은 것은 Big O 표기법 의 수학적 정의를 취할 때 완전히 합리적입니다 .

이제 g ( x )를 1 / x로 쉽게 대체 할 수 있습니다 . 위의 정의는 여전히 일부 f에 대한 것 입니다.

점근 적 런타임 성장을 추정하기 위해 이것은 실행 가능성이 낮습니다. 입력이 증가함에 따라 의미있는 알고리즘이 더 빨라질 수 없습니다. 물론이를 수행하기 위해 임의의 알고리즘을 구성 할 수 있습니다 (예 : 다음 알고리즘).

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

분명히,이 함수는 입력 크기가 커질수록 시간이 덜 걸립니다. 적어도 하드웨어에 의해 시행되는 제한 (수의 정밀도, sleep기다릴 수있는 최소 시간 , 인수 처리 시간 등)이 될 때까지 :이 제한은 상수 하한이므로 실제로 위 함수는 여전히 런타임 O (1)을 갖습니다 .

그러나 거기에 있는 런타임 (적어도 부분적) 줄일 수 있습니다 사실 실제 알고리즘 입력 크기가 증가합니다. 그러나이 알고리즘은 O (1) 미만의 런타임 동작을 나타내지 않습니다 . 여전히 그들은 흥미 롭습니다. 예를 들어 Horspool 의 매우 간단한 텍스트 검색 알고리즘을 사용 하십시오 . 여기서는 검색 패턴의 길이가 증가함에 따라 예상 런타임이 감소하지만 건초 더미의 길이가 증가하면 런타임이 다시 증가합니다.

답변

A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)