一个看起来是O(n)的function但实际上是O(n^2)

哈喽大家好，今天看到了一个有趣的程序码片段(来源)，这个function的功能就是把一个字串转为全小写，看起来没什麽特别的，写起来也相当直观：

/* 这段程序码有问题 */
void lower(char *s)
{
    size_t i;
    for (i = 0; i < strlen(s); i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a');
}

他看起来就是一个O(n)的function，但实际上却是O(n^2)，这是因为在for回圈的每一次开头，都会重新呼叫strlen(s)，而strlen(s)本身又是一个O(n)的function所以整个for回圈的复杂度就是O(n^2)

为什麽compiler不帮我们自动优化，让strlen(s)算一次就好？
虽然我们人类可以判断出for回圈的每一次递回，strlen(s)的回传值都是不会改变的，但是对於compiler来说这却是一个困难的任务，主要原因在於for回圈的内容牵扯到字串内容的改变，要compiler判断字串是否维持原本的长度太困难了

解决方法：

void lower(char *s)
{
    size_t i;
    size_t len = strlen(s);
    for (i = 0; i < len; i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a');
}

经由人类的判断，把字串长度的计算放到回圈外面