时间复杂度如何不同？ [英] How is time complexity different?

问题描述

如果该值先存储然后使用，它会节省时间吗？

例如;

  while（i  // code 
  

和

  int n = strlen（s）; 
 while（i  // code 
  

时间复杂度对于第二种方法，由于函数的返回值首先被存储然后被使用，从而避免每次进入循环时都调用函数，所以第二种方法的值更低？在第一个例子中，假设 i 被适当地初始化（可能为 0 ）并且递增在循环体中，每次在循环中计算字符串 s 中的字符数，因此如果字符串中有N个字符，则会执行N ² 比较（因为 strlen（）比较字符串中的每个字符与'\0'，并且你将执行显式循环N次，并且每次调用 strlen（） N次>中的循环，使得代码O（N <2>在第二个例子中，再次假设 i 在循环体中被初始化并增加了。 ，你会数t他的字符数一次，所以你会做N个比较，使得代码为O（N）。

优化器是否可以安全地优化对 strlen（）不在循环控制中，取决于循环体中的内容。如果编译器可以看到所有内容，或者可以确定被调用的代码不能合法地修改字符串 s ，那么它可以将调用移动到 strlen（）超出循环控制，从而有效地赋予第二个循环的O（N）性能。 OTOH，如果循环的主体调用一个函数并将一个非const指针传递给函数，那么编译器可能无法假定该字符串是未修改，可能需要在每次迭代时调用 strlen（）。

Does it save time if the value is stored first and then used?
For example;

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

and

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

Is the time complexity lower for the second method as the return value of the function is first stored and then used,thus avoiding calling the function every time it enters the loop?

解决方案

In the first example, assuming i is initialized appropriately (to 0 probably) and is incremented in the loop body, you will count the number of characters in the string s each time around the loop, so if there are N characters in the string, you'll do N² comparisons (because strlen() compares each character in the string against '\0', and you'll do the explicit loop N times, and the loop inside strlen() N times each call), making the code O(N²).

In the second example, again assuming i is initialized and incremented in the loop body, you will count the number of characters once, so you'll do N comparisons, making the code O(N).

Whether the optimizer can safely optimize the calls to strlen() out of the loop control depends on what is in the body of the loop. If the compiler can see everything, or can determine that the called code cannot legitimately modify the string s, then it may be able to move the call to strlen() out of the loop control, effectively giving the O(N) performance of the second loop. OTOH, if the body of the loop calls a function and passes a non-const pointer to s to the function, then the compiler may not be able to assume that the string is unmodified and may have to call strlen() on each iteration.

这篇关于时间复杂度如何不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！