問(wèn)答題

【簡(jiǎn)答題】樹結(jié)構(gòu)下執(zhí)行O（n）條帶路徑壓縮的Union-Find指令能否降到線性即O（n）時(shí)間？

答案： 執(zhí)行O（n）條Unoin-Find指令時(shí)，對(duì)于任意的c，都存在一個(gè)特殊的Unoin-Find指令序列，使得執(zhí)行該序列的時(shí)...
題目列表

你可能感興趣的試題

問(wèn)答題

【簡(jiǎn)答題】為什么樹結(jié)構(gòu)下執(zhí)行O（n）條帶路徑壓縮的Union-Find指令只需要O（n*G（n））時(shí)間？
答案： 用平攤分析的聚集方法，把O（n）條Find指令的耗費(fèi)分為三類：
1）O（n）條Find指令的根費(fèi)用，
問(wèn)答題

【簡(jiǎn)答題】什么是平攤分析？平攤分析常用的手法有哪幾種？簡(jiǎn)單說(shuō)明這幾種手法的要點(diǎn)。
答案： 考慮n條指令執(zhí)行的最壞時(shí)間復(fù)雜性。即使某些指令執(zhí)行時(shí)具有比較大的代價(jià)，但利用平攤分析后對(duì)整體考慮，可以得到較小的平均代價(jià)...
微信掃碼免費(fèi)搜題