了解大符号-破解编码面试

了解大符号-破解编码面试

简而言之，没有。正确答案是书中的O（kc k）。

在检查完一个字符串以检查其字符是否有序（占用O（k））之后，打印该字符串将仅增加O（k）-这不会改变您的复杂性。

假设测试字符串是否已排序需要进行

a*k

*** 作，而打印则需要进行 *** 作

b*k

。这样，每个字符串的 *** 作总数最多为

(a+b)*k

O（k）。

编辑： 关于问题的第二部分，遍历具有固定长度的所有单词将导致指数级的运行时复杂度，因为存在c
k个这样的单词，其中

c

的大小是字母的大小，也是

k

该单词的长度。