Question

for+n=a(2:end,:)循环次数怎么算的

Answer 1

问：for+n=a(2:end,:)循环次数怎么算的

答：我们把算法所耗费的时间定义为该算法每条语句的频度之和： T(n) = 2n^3 + 3n^2 + 2n + 1 1. 若循环执行一次：i = 1 * 2 = 2 2. 若循环执行一次：i = 2 * 2 = 2^2 3. 若循环执行一次：i = 2 * 2 = 2^3 4. 若循环执行X次：i = 2^x 设语句 i + i * 2 执行次数为x次， 由循环条件i <= n，所以 2^x <= n，所以 x <= log_2 n 2f(n) <= n，即 f(n) <= log_2 n，取最大值，f(n) = log_2 n， 所以该程序段的时间复杂度T(n) = O(log_2 n)。