lineairair가 더 느린 이유를 알아 내려고 시도했습니다.

Question

저는 파이썬의 알고리즘에 대해 설명하고 있습니다. Big-O 표기법으로 약간 고심하고 있습니다. 문제는 k- 가장 작은 수를 찾고 선형 선형이되도록 함수를 개선하는 선형 함수를 만드는 것입니다. 8.463193 초 선형 함수를 기록

import random 
import timeit 

def linear_find_smallest(values): 
    smallest = len(values) 
    for i in values: 
     if smallest > i != 0: 
      smallest = i 
    return smallest 


def loglinear_find_smallest(values): 
    values.sort() 
    smallest = len(values) 
    for i in values: 
     if smallest > i != 0: 
      smallest = i 
      del values[values.index(i):] 
    return smallest 


if __name__ == '__main__': 
    values = random.sample([i for i in range(1, 10000)], len(range(1, 10000))) 
    t = timeit.Timer("linear_find_smallest(%s)" % str(values), 
        setup="from __main__ import linear_find_smallest") 
    print("Lineair: found in %f seconds" % t.timeit(number=1000)) 
    t = timeit.Timer("loglinear_find_smallest(%s)" % str(values), 
        setup="from __main__ import loglinear_find_smallest") 
    print("Log linear: found in %f seconds" % t.timeit(number=1000)) 

그러나, 선형 함수가 1.614513 초에서 실행하고, (나는 가정) :이 생산했습니다. 누군가 내가 여기서 뭔가 잘못하고 있다고 말할 수 있습니까?

Answer 1

우선 정렬 후에는 sort의 정의에서 가장 작은 첫 번째 값을 반환 할 수 있습니다.

def loglinear_find_smallest(values): 
    values.sort() 
    return values[0] 

이제 복잡성에 대한 진정한 질문입니다. 임의리스트가 주어진다면 선형 검색 (O(n))이 가장 작은 것을 찾기 위해 할 수있는 최선의 방법입니다. 이는 검색 전략이 무엇이든 관계없이 가장 작은 값을 확인하는 첫 번째 n-1 장소가 가장 작은 값이 아니도록 사용자가 함수에 대한 입력을 만들 수 있기 때문입니다.

그렇다면 선형 검색보다 빠른 것은 없을 것입니다. 특히, 로그 선형 (O(n log n))은 실제로 더 많은 작업을 수행하기 때문에 이이 더 느리게 보장됩니다. 로그에서 직선적으로보다 직선적으로 빠르기 때문에 어떻게 혼란 스러웠는지 모르겠습니다. 어쩌면 당신은 logarthmic (O(log n))와 혼동했을까요?