RB樹插入循環中的時間複雜度

我對如何計算以下情況的時間複雜度有這個疑問：RB樹插入循環中的時間複雜度

我有一串字符。我想要做的就是循環使用所有字符，併爲每個字符在RB-Tree中插入一個新節點。

這是代碼：

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

現在，樹上的循環之前是空的，我知道，RB-樹插入的時間複雜度爲O（日誌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!)

但我真的不知道這是正確的...

2016-09-11 VeVeVez

['的log（n！）'在'Theta（nlogn）']（http://stackoverflow.com/q/8118221/572670）。 – amit

2 n log n = n log n？（n代表循環，n代表插入的log n） – Nick

時間給定的代碼複雜

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（n日誌（n））的

因此T（N）是O（n日誌（n））的

2016-09-11 19:32:58 Shravan40

回答