字典序消耗的复杂度疑问

Question

字典序要消耗O(s),是不是以依据每个字符串的首字母在字符串'a-z'中的索引号。

Answer 1

liuyubobobo 2020-05-23 05:38:33

抱歉，我没有理解你的问题。

因为字典序是一种顺序定义方式，不是一个算法过程。具体你是针对视频什么位置提出的问题？

"是不是以依据每个字符串的首字母在字符串'a-z'中的索引号"这句话是什么意思？

• 提问者 weixin_精慕门7573170 #1

  0-9a-z就是字典里字母的顺序。字典序排列我理解就是按照首字母或前几个字母在0-9或a-z的顺序排序。
  视频15:49-16:19中说字符串比较的复杂度是O(s),我理解是看他们在字典字母中的位置先后就，实现上因为比较一个字母是O(1)也即看他在0-9a-z这个顺序中的位置，最多要比较O(s)次，因为可能前几个字母可能一样只有最后一个字母不一样。

• liuyubobobo 回复 提问者 weixin_精慕门7573170 #2

  对！所以比较两个字符的大小顺序，是 O(s) 的。在最差情况下，整个字符串要被扫描一遍！：）