как вы вычисляете сложность в нотации 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). Вы можете настроить временную сложность, умножив против нее. Но по именам методов это звучит так, как их временная сложность будет основана на длине строки, это будет еще одна другая входная переменная.

Так что это не ясный ответ, потому что вопрос не совсем ясен, но я попытался сломать для вас все, что мог.