[解決済み】whileループの時間複雑性(Big O)はどうやったらわかるの？

質問内容

コード 1

int i = 0;
int j = 0;
while(i < n){
     while(j < n){
        printf("{%d,%d}",arr[i],arr[j]);
        j++;
    }
    i++;
    j = 0;
    printf("\n");
}

コード2

int result = 0;
int i = 0;
while (i < n / 2){
    result += arr[i];
    i += 1;
    while (i >= n / 2 && i < n){
        result += arr[i];
        i += 1;
    }
}
printf("%d\n", result);

forループの時間計算の方法だけは知っていますが、whileループについては不明です。 どなたか、各コードの総実行時間を求めるのを手伝っていただけると幸いです。

どのように解決するのですか？

最初のサンプルは、ごく一般的なforループのコードです。その複雑さはO(n^2)です。これは、内側のループの計算量がO(n)であり、それがn回実行されるからである。

2つ目は少し難しいですが、入れ子でないループと同等であることがわかるまで（チェックの複雑さは無視します）。

int result = 0;
int i = 0;
while (i < n){
    result += arr[i];
    i += 1;
}
printf("%d\n", result);

その複雑さはO(n)であることを意味する

時間の複雑さを計算する最も良い方法は、実際にアルゴリズムがどのように動作するかを理解し、演算を数えてみることです。2番目の例では、外側のループが最後の反復を行うまで内側のループは決して実行されません。また、両者は同じコードを実行しているので、全体を1つのループにまとめることができます。

もう一つ良い例がこれです。

for(i=0;i<n;i++){
    for(j=i;j<n;i++){
        //do something
    }
}

操作を数えてみよう。1 + 2 + 3 + 4 + ... + これは、n*n/2となり、O(n^2)となる。