簡介
最近在做算法題丐膝，用SortedSet解決一個區(qū)間添加和區(qū)間刪除問題量愧。不可避免的需要分析一下方法的時間復(fù)雜度。
僅介紹Max帅矗、Min偎肃、GetViewBetween()、Count方法/屬性损晤。Add和Remove肯定是log級別的软棺，因?yàn)楣_的代碼注釋中寫了用的是紅黑樹。
分析參考了公開的代碼尤勋，應(yīng)該是.Net6.0的喘落，看index時間是6月13。（.Net6.0和.Net Framework的實(shí)現(xiàn)好像不同最冰，在Stack Overflow上有人提到）（https://source.dot.net/#System.Collections/System/Collections/Generic/SortedSet.cs,03df9da9e6b0283e）
方法/屬性
Max, Min
O(logn)瘦棋，每次獲取時從根一路向右或一路向下
GetViewBetween(left, right)
O(logn)，調(diào)用會從this的root遍歷得到給定范圍([left, right])中的根元素暖哨，就算初始化完成赌朋。
注1：返回的是SortedSet.TreeSubSet，一些屬性的獲取時間復(fù)雜度和主Set區(qū)別較大
注2：早期的實(shí)現(xiàn)好像會在創(chuàng)建SubSet的同時計(jì)算Count，導(dǎo)致了時間復(fù)雜度不為log級(有人在Stack Overflow里問“為什么這個方法不是logn”)
Count
O(1)或O(k)沛慢，k是Set中的元素?cái)?shù)量赡若。
O(k)情況主要發(fā)生在GetViewBetween返回的TreeSubSet中，因?yàn)樵谶@種情況下Count不能被remove+add追蹤計(jì)算团甲，所以只能在調(diào)用的時候遍歷一遍子樹去計(jì)算逾冬。
改進(jìn)思路
主要針對Count屬性的計(jì)算。
可以為每個節(jié)點(diǎn)維持一個_nodeNum字段躺苦，記錄以當(dāng)前節(jié)點(diǎn)為子樹的節(jié)點(diǎn)數(shù)量身腻，這樣就可以log級別計(jì)算出SubSet的Count，當(dāng)然也要在每次添加刪除的時候遞歸更新這個字段的值匹厘，需要額外O(logn)的復(fù)雜度嘀趟。但O(logn)+O(logn)=O(logn)
