时间复杂度有何不同？

Question

如果首先存储值然后使用它,是否可以节省时间？
例如;

while(i<strlen(s))
 //code

和

int n = strlen(s);
while(i<n)
 //code

第二种方法的时间复杂度是否较低,因为首先存储然后使用函数的返回值,从而避免每次进入循环时调用函数？

Answer 1

在第一个例子中,假设i被适当地初始化(0可能)并且在循环体中递增,你将s每次在循环中计算字符串中的字符数,所以如果字符串中有N个字符,你将会进行N ²比较(因为strlen()比较字符串中的每个字符'\0',你将进行N次显式循环,strlen()每次调用N次循环),使代码为O(N ²).

在第二个例子中,再次假设i在循环体中初始化并递增,您将计算一次字符数,因此您将进行N次比较,使代码为O(N).

优化器是否可以安全地优化对strlen()循环控制的调用取决于循环体内的内容.如果编译器可以看到所有内容,或者可以确定被调用的代码不能合法地修改字符串s,那么它可能能够将调用strlen()移出循环控制,从而有效地给出第二个循环的O(N)性能.OTOH,如果循环体调用函数并将非const指针传递s给函数,则编译器可能无法假设该字符串未被修改并且可能必须strlen()在每次迭代时调用.