파이썬에서 사전 조회의 시간 복잡도

Question

문자열에 재귀 적으로 부분 문자열을 작성하는 함수가 있습니다. 아무도 이것의 복잡성을 말해 주시겠습니까? 나는 그것의 O (2 * n)을 추측하고있다. 왜냐하면 주어진 n의 입력에 2 개의 * n 부분 문자열이있을 수 있지만 100 % 확신 할 수는 없다.

def build_substrings(string): 
    """ Returns all subsets that can be formed with letters in string. """ 
    result = [] 
    if len(string) == 1: 
     result.append(string) 
    else: 
     for substring in build_substrings(string[:-1]): 
      result.append(substring) 
      substring = substring + string[-1] 
      result.append(substring) 
     result.append(string[-1]) 
    return result 

나는 실제로 내가 새로운 주제를받을 자격이되지 않습니다 생각보다 문제에 있습니다

여기에 코드입니다. 파이썬 (사전의 항목)에서 사전에있는 키를 검색하는 것이 얼마나 복잡한 지 궁금합니다. 도움을 주셔서 감사합니다.

Answer 1

N이 문자열의 길이 인 경우 길이가 1보다 큰 하위 문자열의 수> = 1 < = N은 (N * N + 1)/2입니다.

그래서 시간 복잡도는 최악의 경우에 따라서, O (n)은 해시 함수가 불량 및 충돌을 많이 초래하는 경우이다 (N ** 2)

파이썬 딕셔너리는 해시 맵이다 O 것이다. 그러나 이것은 매우 드문 경우입니다. 추가 된 모든 항목은 동일한 해시를 가지므로 주요 Python 구현에 대해 동일한 체인에 추가되는 것은 극히 드뭅니다. 평균 시간 복잡성은 물론 O (1)입니다.

Answer 2

먼저, 함수를 작성하는 두 가지 방법이 있습니다. 여기

# this one's about the same speed 
import itertools 
def build_substrings_2(s): 
    return [''.join(r) for r in itertools.product(*(['',ch] for ch in s))] 

# this one's about 4 times faster 
def build_substrings_3(s): 
    res = [""] 
    for ch in s: 
     res += [r+ch for r in res] 
    return res 

는 속도를 측정하는 방법은 다음과 같습니다

import matplotlib.pyplot as plt 
from itertools import izip 
import timeit 

xs = range(3, 25) 
fns = ['build_substrings_1', 'build_substrings_2', 'build_substrings_3'] 
res = [(fn, []) for fn in fns] 
for i,s in ((chars,"a"*chars) for chars in xs): 
    ts = [ 
     timeit.Timer(
      '{}({})'.format(fn, repr(s)), 
      'from __main__ import {}'.format(fn) 
     ) 
     for fn in fns 
    ] 
    for t,r in izip(ts, res): 
     r[1].append(min(t.repeat(number=10))) 

fig = plt.figure() 
ax = fig.add_subplot(111, yscale='log') 
for label,dat in res: 
    ax.plot(xs, dat, label=label) 
legend = plt.legend(loc='upper left') 

(Y 축이 초 런타임의 로그입니다, X 축입니다 문자 입력 문자열의 길이)

이고 가장 좋은 다항식 맞춤을 찾는 방법은 다음과 같습니다.

import numpy 

data = [numpy.log10(r[1]) for r in res]  # take log of data 
best = [numpy.polyfit(xs[5:], dat[5:], 1) for dat in data] # find best-fit line 
big_o = [10**(b[0]) for b in best]   # convert slope back to power 

(이 간단한 방법 DSM에 감사합니다!)

[2.0099844256336676, 2.0731239717002787, 2.0204035253442099] 

결과 ... 당신의 기능은 당신이 모든을 찾을 필요 (** N 2.00998) O에 대해