循环内插入 RB 树的时间复杂度

Question

我对如何计算以下情况的时间复杂度有疑问：

我有一串字符。我想要做的是在所有字符上循环，并为每个字符在 RB 树中插入一个新节点。

这是代码：

    int length = strlen(myString);
    for(i=0; i<length; i++)
        insertNodeInTree(myString[i]);

现在，循环前树是空的，我知道插入 RB 树的时间复杂度是 O(log N)，树中有 N 个节点。

在这种情况下，树内的节点数与我的索引 i 的值线性相关。当i=0（第一个元素）我在树中没有节点，当i=n我在树中有n个节点。

所以我的问题是：这段代码的时间复杂度是多少？

我在考虑 O(W * log W)，其中 W 是字符串的长度，但我认为这是完全错误的。然后想到每次迭代的复杂度可能是：

O(log 1) + O(log 2) + .... + O(log W-1) + O(log W) = O(log W!)

但我不太确定这是正确的...

Answer 1

给定代码段的时间复杂度

int length = strlen(myString);
for(i=0; i<length; i++)
    insertNodeInTree(myString[i]);

T(N) = T1(N) + T2(N) ------(1)

T1(N) = O(n) // For calculating the Length of the string

T2(N) = O(log 1) + O(log 2) + .... + O(log n-1) + O(log n)

     `= O(log(n!)) // Insertion into RB Tree.`

现在 T2(N) 在 O(nlog(n))

因此 T(N) 是 O(nlog(n))

Time complexity of RB Tree insertion inside a loop