一个看起来是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');}

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