[解決済み】whileループの時間複雑性とは？

質問内容

whileループの時間複雑性を調べたいのですが、何から手をつけていいのかわかりません。forループの複雑さのクラスを見つける方法は理解していますが、whileループになると完全に分からなくなります。どこから始めればいいのか、何かアドバイスやヒントがあれば教えてください。

以下は問題の例です。

x = 0;
A[n] = some array of length n;
while (x != A[i]) {
   i++;
}

解決方法は？

何かをしなければならないとき n 回、やらなければならない n 回です。を使うことができます。 for ループ、または while ループなど、プログラミング言語（または擬似コード！）が提供するものであれば、何でも構いません。 ざっくり言うと、ビッグO記法は、あなたがしなければならない仕事の量についてコメントし、あなたがそれをどのように行うかは気にしません（もう少しざっくり言うと、入力の増加に伴って行う必要のある仕事の量がどのように増加するかについてコメントしています）。

詳しくは続きをお読みください。

ここが混同されているのでは？ for と while は、繰り返される操作を表現するためのプログラミング言語の構成要素である。

アルゴリズム解析は、実装の言語にとらわれず、アルゴリズムを表現する際に実際に使用する構成要素にはこだわらない。

次のようなことを考えてみてください。

1. Input n
2. Do OperationX n times

ビッグ・オー記法機械は、上記の操作の複雑さをコメントするのに役立ちます。これは多くの場合において役立つ。例えば、上の操作と次の操作の実行時間を比較するのに役立つ。

1. Input n
2. Input m
3. Repeat m OperationX n times.

ビッグ・オー記法では、前者がO(n)、後者がO(m * n)となる（と仮定する）。 OperationX は一定の時間を要する)。

好きなループ構成でコードを書いても問題ない。

for(int i = 0; i < n; i++) {
    operationX;
}

が最初の操作であり

i = j = 0;
while(i < n) {
    j = 0;
    while(j < m) {
      operationX;
      j++;
    }
    i++;
}

2つ目 ビッグ・オー記法では、forとwhileが入れ替わっていたとしても、特に気にすることはない。

A[n] = some array of length n;
for(x = 0;x != A[i];i++) {

}

は for の質問を同じ複雑さで書き直したものです( O(n) ).