-1

文字列を再帰的に指定して部分文字列を作成する関数があります。これの複雑さを教えてください。n の入力が与えられた場合、2 *n の部分文字列が存在する可能性があるため、 O(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

私は実際に、新しいトピックに値しないと思うより多くの質問をしています. Pythonで辞書のキーを検索することの複雑さは何だろうと思っていました(辞書の項目の場合)? 助けてくれてありがとう！

4

2 に答える 2

3

まず、関数を記述する方法が 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]

...あなたの関数は約O(n**2.00998)です

于 2012-06-28T00:31:51.117 に答える
-1

N が文字列の長さの場合、長さ >=1<=N の部分文字列の数は (N * N+1)/2 です。

したがって、時間の複雑さは O(N**2) になります

Python dict はハッシュマップであるため、ハッシュ関数が正しくなく、多くの衝突が発生した場合、最悪のケースは O(n) です。ただし、これは、追加されたすべてのアイテムが同じハッシュを持ち、同じチェーンに追加されるという非常にまれなケースです。これは、主要な Python 実装では非常にありそうもないことです。もちろん、平均時間計算量は O(1) です。

于 2012-06-27T13:21:14.860 に答える