iT邦幫忙

3

一個看起來是O(n)的function但實際上是O(n^2)

c

哈嘍大家好,今天看到了一個有趣的程式碼片段(來源),這個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');
}

經由人類的判斷,把字串長度的計算放到迴圈外面


尚未有邦友留言

立即登入留言