-1

我有一个函数可以递归地构建给定字符串的子字符串。谁能告诉我这有什么复杂性？我猜它是 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

我实际上有更多我认为不值得新话题的问题。我想知道在 Python 中搜索字典中的键的复杂性是什么（如果字典中有项目）？非常感谢您的帮助！

4

2 回答 2

3

首先，这里有另外两种编写函数的方法。

# 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是一个hashmap，因此如果hash函数不好并导致很多冲突，最坏的情况是O(n)。然而，这是一种非常罕见的情况，其中添加的每个项目都具有相同的哈希值，因此被添加到同一个链中，这对于主要的 Python 实现来说是极不可能的。平均时间复杂度当然是 O(1)。

于 2012-06-27T13:21:14.860 回答