私は教科書の中で、アルゴリズムの大きな複雑さを計算するという問題を抱えています。私が困惑している質問の1つは、背中に答えがなく、私はどんな入力にも感謝しています。複雑さ（ビッグOを計算する）
単語のリストを含むリンクリストを含む長さn-1の配列があります。各リンクされたリストは最初に挿入され、次にリンクされたリストの最初の単語を使用すると、配列はクイックソートされます。このアルゴリズムの大きな複雑さは何ですか？
私はすでにそれを知っている：
は、リンクリストを横断O（n）の 挿入ソートはO（N^2） クイックソートされる（nlogn）
です私はどのようにちょうどよく分かりませんアルゴリズム全体
の複雑さを計算することについて移動する。これはO(n) * O(m^2)、またはO(n*m^2)の複雑さになり
「を各リンクリストを最初の挿入がソートされます」 - 各リストの長さはリストの数に関係しないため、別の文字を使用する必要があります。
はO(n log n)を追加することに
を "その配列をquicksortedさ"。
合計：O(n*m^2 + n log n)これは、O(n*m^2)を意味する（n log nは、n*m^2と比較して有意ではない）。
私はbig-O表記の専門家ではないので、私が間違っていると私にはあまり厳しくしないでください：p –
技術的に言えば、O（max（nm^2、nlogn））が必要です。さらに、クイックソートは最悪のケースではO（n^2）です。これが平均的なケースの分析でないと、O（max（nm^2、n^2））に答えるのは技術的に正しいでしょう。ただ言って。最悪の場合のO（nlogn）アルゴリズムが必要な場合、マージまたはヒープソートを試してみてください。 – Patrick87
リストに挿入するにはn^2、その後ソートするにはnlg（n）が必要です。これをn-1回（right？）するつもりです。そうです：（n-1）* （n^2 + n * lg（n））=〜n^3 + n^2 * lg（n） – macduff
あなたの質問は、配列がサイズn-1であり、すべてのリンクされたリストがサイズnであることを意味します。あれは正しいですか？ – hatchet