問答題

【簡答題】為什么樹結(jié)構(gòu)下執(zhí)行O（n）條帶路徑壓縮的Union-Find指令只需要O（n*G（n））時間？

答案： 用平攤分析的聚集方法，把O（n）條Find指令的耗費分為三類：
1）O（n）條Find指令的根費用，
題目列表

你可能感興趣的試題

問答題

【簡答題】什么是平攤分析？平攤分析常用的手法有哪幾種？簡單說明這幾種手法的要點。
答案： 考慮n條指令執(zhí)行的最壞時間復雜性。即使某些指令執(zhí)行時具有比較大的代價，但利用平攤分析后對整體考慮，可以得到較小的平均代價...
問答題

【簡答題】簡單不相交集的合并算法中為什么要引進集合的外部名和內(nèi)部名？
答案： 若沒有內(nèi)部名，則每次合并時兩個集合中的所有元素均要改名（改為K），這樣，在n-1次Union中改名的時間就變?yōu)镺（n
微信掃碼免費搜題