問題タブ [complexity-theory]

重複の可能性:
O(1/n) アルゴリズムはありますか?

あなたのコードが O(1) 未満の Big O になる可能性はありますか?

銀行家のアルゴリズムを使用して、リソースに対するすべての要求がデッドロックを引き起こすことなく満たされるかどうかを判断します。

m はリソース タイプの総数です。

n はプロセスの総数です

NEED はサイズ m * n の配列で、リソース タイプごとに保留中のリクエストを定義します。例: NEEDij = 2 は、プロセス i がリソース j の 2 つのアイテムを要求していることを意味します。

アルゴリズムを以下に示します。

私の質問は、時間の複雑さ 0(n * n * m) はどうですか? より具体的には、m 項はどのように多項式に入るのですか? 長さ m のベクトルで要素ごとの比較を行う必要があるためですか?

接尾辞ツリーを構築するための Ukkonen のアルゴリズムを使用していくつかの作業を行っていますが、線形時間の複雑さについての著者の説明の一部を理解していません。

私はアルゴリズムを学び、それをコーディングしましたが、私が主な情報源として使用している論文 (以下にリンク) は、いくつかの部分で少し混乱しているため、アルゴリズムが線形である理由がよくわかりません。

何か助けはありますか？ありがとう。

Ukkonen の論文へのリンク: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

私が使用した擬似コード：

私の理解によると：

• 1行目：実行V-1回数。
• 2行目：すべての頂点の次数の合計時間…..つまり2E時間

2行目ごとに2行目と4行目は、すべてのエッジを1つずつlog E追加/削除しているため、時間がかかります。PQ

したがって、合計time= V-1+2E.logE=E.log E

しかし、本はそれがそうだと言っていE.logVます、それがなぜであるか説明できますか？

2 つの文字列を結合する必要がある場合は、String.Format (コード内の複数の場所で発生する場合は StringBuilder) を使用します。

一部の優れたプログラマーは、文字列の結合の複雑さに注意を払わず、'+' 演算子のみを使用しているようです。

「+」演算子を使用すると、アプリケーションがより多くのメモリを使用するようになることはわかっていますが、複雑さはどうでしょうか?

私はObjective-C、Cocoa、Xcode、InterfaceBuilderを初めて使用します。私は過去にCのバックグラウンドを持っており、RealBASICの経験もかなりあります。

私はMarkとLaMarcheのiPhone3Devの本を読んでいますが、退屈なものがあることに本当に驚いています。多分誰かが私のためにこれにいくつかの光を当てることができます。私の質問は、一見単純なアクションのプロセスに、なぜこのような複雑な数のステップが含まれるのかということです。後で好きになる複雑さにはメリットがありますか？それとも、避けられないのは単なる野蛮な事実ですか？

たとえば、RealBASICで、スライダーの値をテキストボックスに表示したい場合は、次を追加するだけです。

スライダーのChangedイベントに移動します。これは1分足らずでプログラムできます。

Xcode / Interface Builderでは、テキストボックスとスライダーの両方の宣言を物理的に入力してから、それぞれのプロパティ/アウトレット宣言も入力し、ValueChangedのメソッド宣言と実装を作成してから、 （比較的）initWithFormatを使用したスライダーの整数値のNSStringへの複雑な型キャスト。次に、Interface Builderに戻って、入力したコントロールとメソッドのアウトレットにコントロールをリンクする必要があります。これを10分以内に実行する方法がわかりません。多分5。

それで、これの利点は何ですか？Interface Builderが、メソッド宣言と実装だけでなく、コントロール宣言と@propertyステートメントを自動的に作成しない、または少なくとも提案しないのはなぜですか？IBのスライダーをダブルクリックすると、イベントのリストが表示され、.hファイルと.mファイルにスケルトンメソッドが自動的に挿入されるのはなぜですか？そして、なぜIBは別のアプリケーションである必要があるのでしょうか。

私はこれのいくつかがXcodeのすべてに不慣れであるということを受け入れたいと思っていますが、これは開発環境と同じくらい効率的ですか？

これが完全なアグロで反対側の死んだ馬、炎の餌のトピックであるならば、私の謝罪。もしそうなら、「はい、そうです」と言って先に進んでください。

ありがとう、-Rob

このnの関数の複雑さ（Big O）を教えてもらえますか？

これは実際、私と私の友人の間の議論です。私の立場：複雑さはO（n * log（n））友人の立場：log（n）

ご回答ありがとうございます。

C++STL アルゴリズムに関する Nicolai Josuttis の本を読んでいます。stable_sort() などの多くのアルゴリズムでは、アルゴリズムの複雑さは、十分なメモリが利用可能な場合は n * log(n)、そうでない場合は n * log(n) * log(n) であると述べています。私の質問は、メモリ使用量が複雑さにどのように影響するかです。そして、STL はそのような状況をどのように検出するのでしょうか?

私の大学の離散数学コースでは、教師が学生にアッカーマン関数を示し、紙の上で関数を開発するよう学生に割り当てます。

再帰最適化のベンチマークであることに加えて、アッカーマン関数には実際の用途がありますか?