(1)

Question

데프 검색 (LST, 배) :

for item in lst: 

    if item == x: 

    return True 

    return False 

허용 입력이 만든 길이 N의 임의의 목록 인 경우 012, 1, 2, ... 10의 무작위 요소의 확대
평균 런타임이 big-theta (1)임을 증명하는 방법

나는 많은 방법을 시도했지만, Θ (n)

Answer 1

임의의 방법이 균일하면, 예상되는리스트의 1은 n/10이고 예상되는 2는 n/10입니다. 다시 균일 무작위에 기반하여 최악의 경우에 10 개의 원소를 검사 한 후에 x를 찾을 것을 기대합니다. 따라서이 방법은 예상되는 일정 시간 값을 가지며 복잡도는 Tetha (1)입니다.