我的算法的时间复杂度计算

Question

给定一个字符串，找到第一个不重复的字符并返回它的索引。如果不存在，则返回-1。你可以假设该字符串只包含小写字母。

我将定义一个哈希表来跟踪字符的出现次数。从左到右遍历字符串，检查当前字符是否在哈希表中，如果是则继续，否则在另一个循环中遍历其余部分的字符串以查看当前字符是否存在。如果不存在，则返回索引并更新哈希表。

def firstUniqChar(s):

    track = {}
    for index, i in enumerate(s):
        if i in track:
            continue
        elif i in s[index+1:]: # For the last element, i in [] holds False
            track[i] = 1
            continue
        else:
            return index
    return -1

firstUniqChar('timecomplexity')

我的算法时间复杂度是什么（平均和最坏情况）？

- Nicholas

---

找到第一个不重复的字符 - 这是否意味着对于 abbacdec，算法会返回 a（它不会 _重复_），还是返回 d（它只出现 _一次_）？ - miraculixx

非重复意味着仅存在一次@miraculixx，在你的情况下，返回5。 - Nicholas

Answer 1

您的算法时间复杂度为O(kn)，其中k是字符串中唯一字符的数量。如果k是一个常数，那么它就是O(n)。由于问题描述明确定义了元素的替代方案数量的上限（“假设是小写（ASCII）字母”），因此k是一个常数，您的算法在这个问题上运行时的时间复杂度是O(n)。即使n会无限增长，您也只会对字符串进行O(1)次切片，因此您的算法始终保持为O(n)。如果移除track，则它将成为O(n²)：

In [36]: s = 'abcdefghijklmnopqrstuvwxyz' * 10000

In [37]: %timeit firstUniqChar(s)
100 loops, best of 3: 18.2 ms per loop

In [38]: s = 'abcdefghijklmnopqrstuvwxyz' * 20000

In [37]: %timeit firstUniqChar(s)
10 loops, best of 3: 36.3 ms per loop

In [38]: s = 'timecomplexity' * 40000 + 'a'

In [39]: %timeit firstUniqChar(s)
10 loops, best of 3: 73.3 ms per loop

在这里，T(n)的时间复杂度依然是O(n)，它与字符串中字符数量呈线性关系，即使这是算法的最坏情况 - 没有任何一个字符是唯一的。

---

我将介绍一种不太高效但简单且智能的方法：首先使用collections.Counter计数字符直方图，然后遍历字符找到其中一个

from collections import Counter
def first_uniq_char_ultra_smart(s):
    counts = Counter(s)
    for i, c in enumerate(s):
        if counts[c] == 1:
            return i

    return -1

first_uniq_char('timecomplexity')

这个算法的时间复杂度为O(n)；Counter在O(n)时间内计数直方图，我们需要再次枚举字符串中的O(n)个字符。然而，在实践中，我相信我的算法具有较低的常数，因为它使用了标准字典来计数Counter。

让我们设计一个非常愚蠢的暴力算法。由于可以假设字符串仅包含小写字母，因此利用这一假设：

import string
def first_uniq_char_very_stupid(s):
    indexes = []
    for c in string.ascii_lowercase:
        if s.count(c) == 1:
            indexes.append(s.find(c))

    # default=-1 is Python 3 only
    return min(indexes, default=-1)

让我们在Python 3.5上测试我的算法和其他答案中发现的一些算法。我选择了一个对我的算法来说非常糟糕的情况:

In [30]: s = 'timecomplexity' * 10000 + 'a'

In [31]: %timeit first_uniq_char_ultra_smart(s)
10 loops, best of 3: 35 ms per loop

In [32]: %timeit karin(s)
100 loops, best of 3: 11.7 ms per loop

In [33]: %timeit john(s)
100 loops, best of 3: 9.92 ms per loop

In [34]: %timeit nicholas(s)
100 loops, best of 3: 10.4 ms per loop

In [35]: %timeit first_uniq_char_very_stupid(s)
1000 loops, best of 3: 1.55 ms per loop

因为它在结尾找到了a并退出，所以我的愚蠢算法是最快的。而我的聪明算法最慢。除了这种最坏情况外，我的算法表现不佳的另一个原因是，在Python3.5上，OrderedDict用C语言编写，而Counter则使用Python语言。

---

让我们进行更好的测试吧：

In [60]: s = string.ascii_lowercase * 10000

In [61]: %timeit nicholas(s)
100 loops, best of 3: 18.3 ms per loop

In [62]: %timeit karin(s)
100 loops, best of 3: 19.6 ms per loop

In [63]: %timeit john(s)
100 loops, best of 3: 18.2 ms per loop

In [64]: %timeit first_uniq_char_very_stupid(s)
100 loops, best of 3: 2.89 ms per loop

看起来，我的“愚蠢”算法并不那么愚蠢，它利用了C语言的速度，同时最大程度地减少了运行Python代码的迭代次数，在这个问题上明显获胜。

- Antti Haapala -- Слава Україні

---

哦，不错。到目前为止，我最喜欢这个了。 - John Zwinck

@JohnZwinck 实际上这比Karin的慢，有趣的是，我以为OrderedDict会更慢。 - Antti Haapala -- Слава Україні

有趣的是，我现在仍然感到惊讶，我的算法在你的情况和我分配的某些其他 s中比你的更快（因为你说Counter是用Python编写的）。 我建议你也在Jupyter中计时我的代码。 实际上，我非常确定我的算法的最坏情况是O(n^2)，但我更感兴趣的是平均时间复杂度（似乎没有人明确回答），因为我发现这里的问题非常依赖于案例，即它似乎很大程度上取决于 s。 - Nicholas

如果计数器的实现方式不是现在这样的话，我的程序速度可能会快3-4倍。 - Antti Haapala -- Слава Україні

@NicholasLiu 修改了我的答案，你的算法运行时间为O(n)。 - Antti Haapala -- Слава Україні

真是我想要的，非常感谢你的时间！但是我认为k是重复字符的数量加1。我在考虑当n很大时，我们预计在遇到第一个独特的字母之前会遇到每个重复的字母。每次我们遇到一个新的重复字母，需要O(n)的时间。再加上第一个独特字母还需要O(n)，然后结束。 - Nicholas

Answer 2

正如其他人所指出的那样，由于嵌套的线性搜索，您的算法是O(n²)。正如@Antti发现的那样，OP的算法是线性的，并且受到O(kn)的限制，其中k是所有可能的小写字母的数量。

我提出一个O(n)解决方案：

from collections import OrderedDict

def first_unique_char(string):
    duplicated = OrderedDict()  # ordered dict of char to boolean indicating duplicate existence
    for s in string:
        duplicated[s] = s in duplicated

    for char, is_duplicate in duplicated.items():
        if not is_duplicate:
            return string.find(char)
    return -1

print(first_unique_char('timecomplexity'))  # 4

- Karin

---

你的返回值是索引，而不是字符 :) - Antti Haapala -- Слава Україні

哈哈，谢谢你的帮助！我只是真的想保留 duplicated[s] = s in duplicated，差点心碎了！ - Karin

@friendlydog duplicated 是一个有序字典，因此如果存在重复字符，则它不会包含原始字符串中所有的字母。这意味着索引可能与原始字符串不匹配。 - Karin

啊，我明白了。我的错误。 - user6732794

实际上，OP的原始算法是O(n)。 - Antti Haapala -- Слава Україні

Answer 3

你的算法是O(n²)，因为你在循环s时，又有一个“隐藏”的循环迭代了一部分s。

一个更快的算法应该是：

def first_unique_character(s):
    good = {} # char:idx
    bad = set() # char
    for index, ch in enumerate(s):
        if ch in bad:
            continue
        if ch in good: # new repeat
            bad.add(ch)
            del good[ch]
        else:
            good[ch] = index

    if not good:
        return -1

    return min(good.values())

这是O(n)的，因为in查找使用哈希表，而不同字符的数量应该远小于len(s)。

- John Zwinck

---

目前还不是完全的O(n)，因为sorted的时间复杂度是O(n log n)，详见Python TimeComplexity。但效率已经有所提高。 - miraculixx

将sorted(good.values())[0]替换为min(good.values())（在Python 2.x中使用good.viewvalues()避免临时列表），就可以回到O(n)。请注意，排序步骤在非重复值的数量方面是O(n log n)，这可能比总字符串大小（即其他大O中的n）要小得多，因此它可能不是很大，但是，min直接执行您想要的操作，并保证与大O成本无关的工作（因为主算法在字符串长度上是O(n)，而min步骤在较小的n上是O(n)）。 - ShadowRanger

@miraculixx：Python的set和dict是使用哈希表实现的；是的，哈希表的最坏查找成本为O(n)，但在Python中单个字符的哈希冲突是不可能的（完整的Unicode空间大小目前<21位，我相信Python的哈希码在所有版本上至少为32位，在64位版本上为64位），因此冲突只会是桶冲突与不匹配的哈希值，而随着dict的增长，重新哈希会使一个尺寸的冲突在更大的尺寸上消失。实际上，查找将是O(1)。 - ShadowRanger

所以，你说的“O(n^2)”在技术上确实是最坏情况，但要触发它几乎是非常困难甚至不可能的，而且通常在Python中不值得担心这种可能性，特别是在现代的Python 3中（其中长度超过某个阈值的字符串使用具有每次启动解释器的密钥的密码学安全哈希算法，这意味着在一个会话中发生碰撞的键在另一个会话中不会碰撞，并且使故意触发哈希碰撞的拒绝服务攻击成为可能的非问题）。只需将dict和set视为"O(1)，但常数因子较高"即可。 - ShadowRanger

@ShadowRanger 是的，但是大O表示法是最坏情况下的视角，在最坏情况下，所有字符都会出现在“good”中，因此排序的时间复杂度为O(n log n)。此外，根据Python时间复杂度，集合和字典查找的最坏情况时间复杂度为O(n)，而不是O(1)，尽管我认为这确实取决于实际实现。平均和最佳情况下我同意。 - miraculixx