算法的运行时间也是随机的 Different runs of A on an input x may also have different lengths,i.e.,they may have different costs.So,the time complexity becomes a random variable. Time(c)到底是什么意思？ Let Time(C)10 be the time complexity of the run C of A on z.Then the expected time complexity of A on x is Erp-TmeA(r）=E(Time]=ProbA,.z(C)·Time(C)
算法的运行时间也是随机的 Time(C)到底是什么意思？
以下两套评价体系均可用于评估随机算法 时间复杂度 Ep-TimeA()=E[Time=∑ProbA,z(C)·Time(C), Exp-TimeA(n)=max {Exp-TimeA(x)|x is an input of size n} TimeA()=max {Time(C)C is a run of A on x}. TimeA(n)=max {TimeA(x)x is an input of size n}
以下两套评价体系均可用于评估随机算法 时间复杂度