Python - 색인 위치 찾기 기능

다음 함수의 복잡도는 무엇입니까 ??Python - 색인 위치 찾기 기능

def find_set(string, chars): 
    schars = set(chars) 
    for i, c in enumerate(string): 
     if c in schars: 
      return i 
    return -1 

print(find_set("Happy birthday", "py"))

이 경우, H는 CHEERIO의 인덱스 1에 있기 때문에 1이 리턴됩니다.

이 기능을 더 최적화 할 수 있습니까?

출처

2015-02-03 user3624831

귀하의 (최악의 경우) 시간 복잡도는 O(len(string) * len(set))입니다. 예, 적어도 알고리즘 관점에서 더 잘할 수 있습니다.

def find_set(string, chars): 
    schars = set(chars) 
    return next((i for i, c in enumerate(string) if c in schars), -1)

이 O(len(chars) + len(string)) (최악의 경우)에 실행한다. 물론, "최적화"에 관해서는 대개 자신이 알고 있고 생각하는 것을 잊어 버려야합니다. 광산의 알고리즘 복잡성이 더 좋다고해서 현실 세계 데이터 인이 에서 더 잘 수행된다는 것을 의미하지는 않습니다.

출처

2015-02-03 00:19:18 mgilson

@ITellMyselfSecrets - 생성기가 항목을 생성하지 않으면 'next'는 기본적으로 StopIteration을 발생시킵니다. 이를 억제하고 두 번째 인수를 제공하여 특정 값을 반환하도록 'next'를 알릴 수 있습니다. [the docs] (https://docs.python.org/2/library/functions.html#next)를 참조하십시오. – mgilson

정말 고마워요. for 루프를 설명해 주시겠습니까? 나는 그것을 해독하는 데 어려움을 겪고있다. – user3624831

@ user3624831 - 발전기 표현입니다. 먼저, 문자열을 열거합니다. 이 형식 (인덱스, 문자)의 2 튜플을 생성합니다. 그 튜플을'i, c'에 압축을 풉니 다. 나는'c'가 문자 집합'에 있다면 '를보고, 만약 있다면'i' (인덱스)를 반환합니다. 내장 된'next' 함수는 리턴 된 첫 번째 것을 뽑아냅니다 (그리고 나머지는 신경 쓰지 않습니다). _nothing_이 나오면'next'는 "default"-이 경우 -1을 반환합니다. – mgilson

Python - 색인 위치 찾기 기능

답변

관련 문제