7.4 技术解惑

7.4.1 循环中的低效问题

先看下面的代码。

    for (I = 0; i <    strlen(str); I ++)
    //处理str[i];

请问这个循环的时间复杂度是多少？如果你的回答是O（n），那你就太粗心了，事实上它是O(n*n)。不要惊奇，事实上这个时间复杂度是在循环条件中调用strlen函数产生的。在C语言中我们经常用以’\0’为结尾字符的字符数组表示字符串，strlen就是求解用这种逻辑表示字符串的长度的，它的实现方法就是从第1个字符开始向后找，直到找到字符’\0’为止，它的复杂度为O(n)，而对它的调用是在循环条件中，循环次数为n，条件会判断（n+1）次，因此说这段代码的时间复杂度为O(n*n)。

不要指望编译器能对代码进行优化从而把对strlen的调用提到循环以外，这是很难的，因为strlen不是一个简单的算术表达式而是一个函数调用，所以编译器不知道它是不是有副作用，如果有副作用，则一次调用和多次调用的结果是不一样的。因此编译器只好完全按照代码告诉它的逻辑多次执行strlen。

在一般情况下，较好的写法是：

    char * temp;
    for (temp = str; *temp ! = '\0'; temp ++)
    *temp  ...

接下来的代码如下。

    int slen = strlen(str);
    for(i = 0; i < slen; i    ++
    str[i]...

在大多数情况下，如果循环条件中有一个函数调用，那么它的返回值是不会在循环条件中改变的，一定要把它拿到循环外面来。