如何从代码片段推导时间复杂度T(n)的计算方程?
代码时间复杂度T(n)推导问题
我没法把代码片段转化为计算对应T(n)的方程,举几个例子说明我的问题:
示例1:简单赋值代码
a = b + c; d = a + e;
不知道怎么确定这段代码的T(n)。
示例2:嵌套循环代码
sum = 0; for (i=0; i<3; i++) for (j=0; j<n; j++) sum++;
我参考过同类问题的示例和说明,但还是搞不懂具体的方程推导方式。
已知结果但看不懂推导的示例
代码如下:
sum = 0; i = 1; while (i <= N) { sum = sum + 1; i++; }
已知这个代码的T(N)推导过程是:T(N) = 2 + (Σ 上限为N,下限为i=1) * 2,最终化简为2+2N,但我完全不理解这个推导过程。
内容的提问来源于stack exchange,提问作者Joseph Decker
相关产品推荐
相关产品推荐

