問題タブ [asymptotic-complexity]

明日の中間試験に向けて勉強していますが、これらの時間の複雑さに苦労しています。本の簡単な例と、この例について説明します

交換ソート

この Exchange の並べ替えの「Every-Case Time Complexity」についてjは、基本的な操作 (交換) があるため、for ループを分析する部分がほとんど理解できます。したがって、パスの総数をリストすると、次のようになります。

今私の質問は... 1 はどこから来たのですか? だと思いましたn-1 + n-2 +... + n。

さらに、私が本当に理解していないのは、(n-1)n/2.
それは明らかに私が中期的に考え出さなければならないものであり、それを見ると、直感的には思い浮かびません..など(n-1)n/2を思いつく方法を理解しています.T(n) = (n-1) + (n-2)

明日の中間試験でこのような答えを思いつくことができるように、誰かがこれを素人の言葉で説明してもらえますか?

単調ではない最悪のケースの動作をする自然なプログラムまたはアルゴリズムを知っている人はいますか?

単調ではない最悪の場合の動作とは、サイズ n+1 の入力の最悪の場合の実行時間が、サイズ n の入力の場合の最悪の場合の実行よりも短くなる自然数 n が存在することを意味します。

もちろん、この振る舞いでプログラムを構築するのは簡単です。これは、自然なプログラムの小さな n (n = 1 など) で発生する場合もあります。しかし、大きな n に対して単調ではない便利なアルゴリズムに興味があります。

最近、私はCLRSのすべての演習を解決しようとしています。しかし、私が理解できないものがいくつかあります。CLRS演習12.4-2からのそれらの1つは次のとおりです。

ツリー内のノードの平均深さがΘ（lg n）であるが、ツリーの高さがω（lg n）であるように、n個のノードで二分探索木を記述します。ノードの平均深さがΘ（lgn）であるnノード二分探索木の高さに漸近的な上限を与えます。

この問題を解決するためのアイデアや参考資料を誰かが共有できますか？ありがとう。

長さ n の n 個の文字列のリストは、マージ ソート アルゴリズムを使用して辞書順にソートされます。この計算の最悪の場合の実行時間は?

宿題としてこの質問を受けました。O(nlogn)時間でマージソートソートを知っています。長さの辞書式順序では、 nlogn の n 倍ですか? または n^2 ?

したがって、リスト内の最大要素を見つけるには、O(n) 時間の複雑さがかかります (リストに n 要素がある場合)。より高速に見えるアルゴリズムを実装しようとしました。

これは実際に高速ですか？漸近的な時間の複雑さは (タイト バウンド) であると思いますか?

私は自分自身にスキームを教えようとしています、そして私が最も苦労している概念は空間と時間の複雑さです。この章の終わりにいくつかの演習を行っていましたが、次の2つを理解できませんでした。私は、各関数の漸近的な時間計算量（タイトバウンド）を理解しようとしています。

このため、停止条件が満たされない限り、反復関数を毎回1回呼び出すため、漸近時間計算量はO（n）であると考えました。

2番目の関数は次のように与えられます。

これは私にはO（n ^ 2）のように見えました。なぜそう思うのか説明が難しいので、本当に目が離せません。

これは、MIT OpenCourseアルゴリズム入門の割り当てによる漸近表記の問題です 。次の各ステートメントについて、漸近的に非負の関数fおよびgについて、常に真であるか、決して真ではないか、場合によっては真であるかを判断します。それが常に真実であるか、決して真実ではない場合は、その理由を説明してください。時々真である場合は、それが真である例と偽である例を1つ挙げてください。

私はそれが決して真実ではないと思います。これが私の証拠です：

結果はと矛盾しg(n) ≠ O(f(n)) (Big-O note)ます。同じく、

これはと矛盾しf(n) ≠ O(g(n)) (Big-O note)ます。

解決策はそれが時々真実であると言います：

証明のどこで間違ったことをしましたか？また、解決策がわかりません。私にはベクトルノルム||n*sin(n)||のように見えます。

m個の要素を挿入する最初は空のRBツリーについて考えてみます。要素の挿入にはO（log n）時間がかかります。ここで、nは現在挿入されている要素の数です。したがって、m個の挿入の合計時間を次のように記述できます。sumlog（i）for i = 1..m == log（Pochhammer（1、m）;礼儀WolframAlpha。

確かに、m * logmとlog（Pochhammer（1、m）の比率は1に収束するので、これまでlog--Pochhammerを見たことがないのはそのためだと思います。

コンピュータサイエンスで使用されている他の「エキゾチック」な機能は何ですか？私はinverse-ackermanがUnion-Findなどに表示されることを知っています...

多段グラフ問題については、「FundamentalsofComputerAlgorithms」の本を調べていました。

それは言う：

著者は、複雑さはO（| V | + | E |）であると述べています。ここで|V| は頂点の数であり、| E | はエッジの数です。

forループは頂点の総数に対して実行され、内側の線は近端を選択する必要があることを知っています。

背後にある論理を理解できませんでした

私がここでlittle-oを求めていることに注意してください（ここで同様の質問を参照してください）-大きなOhの場合は明らかに間違っています-little-oの場合は正しいと感じますが、それを証明できないようです...

編集：私が議論を提起したことをうれしく思います:)簡単にするためにf、g>0と仮定します