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)があることを意味します。したがって、全体的な時間の複雑さは2つの入力に依存し、より大きなものに拘束されます。

SubWord()またはRotWord()は、一定時間でないものがあれば、O(EXPANDED_KEY_COUNT)部分のコードに影響します。時間の複雑さを乗算して調整することができます。しかし、メソッドの名前によって、時間の複雑さは文字列の長さに基づいているように聞こえますが、さらに別の入力変数になります。

質問が完全にはっきりしていないので、これは明確な答えではありませんが、私は可能な限りあなたのために物事を分解しようとしました。