源码中关于复杂度的错误

[ssjssh]

我在看redis中的跳跃表的实现，觉得注释中对于复杂度的记录是有问题的。

` *

• T = O(N)
  */
  int zslRandomLevel(void) {
  int level = 1;

  while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
  level += 1;

  return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
  }`
  这里的复杂度是O(N)，但是应该是O(ZSKIPLIST_MAXLEVEL)。由于在算法中复杂度计算的时候会忽略常数，因此这个函数的复杂度其实是O(1),当然需要假设random的复杂度是O(1).

还有跳跃表的插入和删除在代码中都是O(Nlog(N)),而查找的复杂度是O(log(N))。但是跳跃表的插入和查找的复杂度其实是一样的，都是最好O(log(N))，最坏O(N)。这点维基也有写，希望您能改下。

当时看到这个地方的时候确实很让人迷惑。

[ccoder64]

同样疑惑。
过来确认的时候发现，15年以后就没更新了。。

[hfdpx]

同样的疑惑，过来确认一下我没错

[vicksiyi]

sds sdstrim(sds s, const char *cset)
{
struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));
char *start, *end, *sp, *ep;
size_t len;

// 设置和记录指针
sp = start = s;
ep = end = s + sdslen(s) - 1;

// 修剪, T = O(N^2)  ===========================>这里是不是也错了？？？
while (sp <= end && strchr(cset, *sp))
    sp++;
while (ep > start && strchr(cset, *ep))
    ep--;

// 计算 trim 完毕之后剩余的字符串长度
len = (sp > ep) ? 0 : ((ep - sp) + 1);

// 如果有需要，前移字符串内容
// T = O(N)
if (sh->buf != sp)
    memmove(sh->buf, sp, len);

// 添加终结符
sh->buf[len] = '\0';

// 更新属性
sh->free = sh->free + (sh->len - len);
sh->len = len;

// 返回修剪后的 sds
return s;

}