この関数の時間複雑度はどのくらいですか？

Question

私の機能の時間の複雑さについて質問したいと思います。以下はC++で書かれた私の関数です。

void List::swap(List& other) 
{ 
    List temp; 
    Iterator r = begin(); 
    Iterator i = other.begin(); 

    while(!i.equals(other.end())) 
    { 
     temp.push_back(i.position->data); 
     i = other.erase(i); 
    } 

    while(!r.equals(end())) 
    { 
     other.push_back(r.position->data); 
     r = erase(r); 
    } 

    r = temp.begin(); 
    for(r; !r.equals(temp.end()); r.next()) 
    { 
     push_back(r.position->data); 
    } 
} 

機能の目的は、2つのリンクされたリストの要素を交換することです。演習では、この関数をO（1）時間に実行する必要があります。私は3つのループを使用していたので、私は鉱山の機能の時間の複雑さをどのように正確に数えるのかよく分かりませんでした。

Answer 1

Big Oh表記について話しているので、複雑さは最大値（ループ1の複雑さ、ループ2の複雑さ、ループ3の複雑さ）になります。 3つのループを使用しているので、複雑さはO（1）ではありません。 ヒント：これらはリンクリストなので、ヘッドポインタを交換するだけで済みます。

Answer 2

成長の順序は、問題の複雑さの上限と考えることができます。

最初のループはO（this.size（））

第3のループはO（other.size（））であるループはO（other.size（））

秒です

O（m + n）またはO（n）としてO表記でより正確に記述されるO（2 * other.size（）+ this.size 2つのリストのサイズは互いに独立しています。