你如何计算 Big-O 符号的复杂性？任何人都可以在下面的这段代码中解释一下

Question

void KeyExpansion(unsigned char key[N_KEYS], unsigned int* w)
{
    unsigned int temp;
    for(int i=0; i< N_KEYS; i++)
    {
        w[i] = (key[N_KEYS*i]<<24) + (key[N_KEYS*i+1]<<16) + (key[N_KEYS*i+2]<<8) + key[N_KEYS*i+3];
    }

    for(int i = 4; i< EXPANDED_KEY_COUNT; i++) 
    {
        temp = w[i-1];
        if(i % 4 == 0)
            temp = SubWord(RotWord(temp)) ^ Rcon[i/4];

        w[i] = temp ^ w[i-4] ;
    }
}

Answer 1

Big-O 帮助我们根据输入进行分析。你的问题的问题是似乎有几个输入，它们可能相互关联，也可能不相互关联。

输入变量类似于 N_KEYS 和 EXPANDED_KEY_COUNT。我们也不知道 SubWord() 或 RotWord() 根据提供的内容做什么。

由于未提供 SubWord() 和 RotWord()，为了便于计算，我们假设它们是常量。

你有基本的循环并迭代每个值，所以它非常简单。这意味着您有 O(N_KEYS) + O(EXPANDED_KEY_COUNT)。所以整体时间复杂度取决于两个输入，并且会受较大者的约束。

如果 SubWord() 或 RotWord() 做任何非恒定时间的特殊操作，那么这将影响代码 O(EXPANDED_KEY_COUNT) 部分的时间复杂度。您可以通过乘以它来调整时间复杂度。但是根据方法的名称，听起来它们的时间复杂度将基于字符串的长度，将是另一个不同的输入变量。

所以这不是一个明确的答案，因为问题并不完全清楚，但我已尽力为您分解。