c++ - 最終試験問題演習、「データ構造」クラス

Question

私はデータ構造クラスの最終練習に取り組んでおり、助けを得たいと思っていたいくつかの質問があります。

```
void BST::traverse(Vertex *V)  // post order traversal recursively
{   
  if (V != NULL) 
    {
      traverse(V->Left);        
      traverse(V->Right);       
      cout << V->elem << endl;     
    }
}
```
これを深さ優先検索に変更する必要があります。そうするためには、再帰ごとにルートに再アクセスする必要があると思いますが、ルートを離れることは決してないので混乱しています。おそらく一時的な根？わからない！
リンクリストの実装では、コピーコンストラクターが使用される 2 つの場合について説明する必要があります。関数呼び出しのために呼び出されることは知っています。しかし、別の理由は何ですか？
なぜ大きな O 表記を使用するのですか [たとえば、2n^2 + 3n + 4 の代わりに O(n^2) を使用します)。そうするときに定数を無視することは知っていますが、私ができる答えは他にありますか?
時間と空間の複雑さ。私にとって最も明白なのは、マージソートとクイックソートですが、テストでさらに要求があった場合に備えて、別のソートを考えてもらえますか? 私たちはクラスで非常に多くのことを調べたので、これ以上名前を挙げられないなんて信じられません。

score 4 · Accepted Answer

検索コードを追加するだけで、すでに深さ優先検索です。
BSTaが引数として関数に値で渡される機会がすでにあります。オブジェクトのコピーを作成する別の時間はいつですか? (ヒント: 関数にも関連するものがあります)
whennが大きいため、2 ⁿは方程式の他のものよりもはるかに大きくなるため、定数と他のすべてを除外します。Big-O 表記法は正確であることを意図したものではありません。入力が非常に大きくなるにつれて、問題の解決策がどのように拡大するかを知らせるためだけのものです。十分にn大きくなると、複雑さが非常に大きくなり、他のものが小さくなり、基本的に 2 ⁿになります。
これについては、より具体的にする必要があります。スペースと速度を交換する 2 つのアルゴリズムをお探しですか?

score 1 · Accepted Answer

3 大 O 表記は支配的な用語のみを引用します。n が大きくなると、これが結果の最も重要な部分になります。

4 バブルソートを検討する - 長い時間がかかるので嫌いでしたが、もう 1 つの項目のスペースしか必要としません。

2 に答える 2