- 搜標題
- 搜題干
- 搜選項
問答題
【簡答題】樹結構下執(zhí)行O（n）條帶路徑壓縮的Union-Find指令能否降到線性即O（n）時間？
答案：
執(zhí)行O（n）條Unoin-Find指令時，對于任意的c，都存在一個特殊的Unoin-Find指令序列，使得執(zhí)行該序列的時...
你可能感興趣的試題
問答題
【簡答題】為什么樹結構下執(zhí)行O（n）條帶路徑壓縮的Union-Find指令只需要O（n*G（n））時間？
答案：
用平攤分析的聚集方法，把O（n）條Find指令的耗費分為三類：
1）O（n）條Find指令的根費用，
1）O（n）條Find指令的根費用，
問答題
【簡答題】什么是平攤分析？平攤分析常用的手法有哪幾種？簡單說明這幾種手法的要點。
答案：
考慮n條指令執(zhí)行的最壞時間復雜性。即使某些指令執(zhí)行時具有比較大的代價，但利用平攤分析后對整體考慮，可以得到較小的平均代價...
