算法的效率-所有字符串元素都是唯一的

Question

任务：实现一个算法来确定字符串是否具有所有唯一字符。

我写了两个函数。我该如何开始评估哪一个更好/更高效？要找什么？

这是第一个：

def is_unique(word):
start = 0
len_word = len(word)
while start < len_word:
for i in range(start + 1, len_word):
if word[start] == word[i]:
return False
start += 1
return True

第二个：

def unique_list(word):
unique = []
for i in word:
if i in unique:
return False
else:
unique += i
return True

Answer 1

这两种算法都是低效的：它们的复杂性是O(n^2)，而n是word中的字符数。第二种算法在实践中会快一点，因为它使用了Python内建操作i in unique(而不是缓慢的CPython循环(。

测试可以用一种更快的方式完成：len(set(s)) == len(s)。此行测试字符串是否包含O(n)中的唯一字符(因为字符串字符可以在线性时间中转换为一个集合(。