私がこのような機能を持っていた場合：

それはn^2のBigOですか、それともnのBig Oですか？forループがあり、そのforループ内にそれ自体への関数呼び出しがある場合、Big Oは反復回数に関数を掛けたものですか？

注：私はアルゴリズム分析の超初心者なので、私の断言を絶対的な真実と見なさないでください。私が述べていることは何でも（またはすべて）間違っている可能性があります.

こんにちは、アルゴリズム分析と「Big-O-Notation」について読んでいて、何かに戸惑いました。

char 配列のすべての順列を出力するように求められたとします。[a,b,c] の場合、それらは ab、ac、ba、bc、ca、および cb になります。

それを行う1つの方法は次のとおりです（Javaの場合）：

私が正しければ、このアルゴリズムにはO(n ² )という表記があります。

私はそれを行う他の方法を考えました：

現在、このアルゴリズムは元の よりも 2 倍高速ですが、私が間違っていない限り、big-O 表記ではO( ² )でもあります。

これは正しいです？おそらくそうではないので、言い換えます: どこが間違っていますか??

System.currentTimeMillis（）は、Javaの時間パフォーマンスの最良の尺度ですか？これを使用して、アクションが実行される前の時間とアクションが実行された後の時間を比較する場合の落とし穴はありますか？より良い代替案はありますか？

次のコードがある場合：

メソッドのDosomething(object)時間パフォーマンスはO（log n）ですが、IterateArrayO（n）またはO（n log n）の全体的なパフォーマンスはありますか？

この回答へのコメントでは、単純にリンクされたリストの反転は O(n) 時間ではなく、O(nlog(n)) でしか実行できないという考えが提起されています。

これは間違いなく間違っています。O(n) 反転は問題ではありません。リストをたどってポインタを変更するだけです。3 つの一時ポインターが必要です。これは、一定の余分なメモリです。

O(nlog(n)) は O(n) よりも悪い (遅い) ことを完全に理解しています。

しかし、好奇心から-単純にリンクされたリストを反転するための O(nlog(n)) アルゴリズムは何でしょうか? 一定の余分なメモリを持つアルゴリズムが望ましいです。

編集 2:これが依然として重要である理由の実用的なデモンストレーションについては、 stackoverflow 自身の正規表現による停止 (2016-07-20) を参照してください。

編集：この質問は、私が最初に尋ねたときからかなり進化しました。2 つの高速で互換性があるが、完全な機能を備えていない実装については、以下を参照してください。より多くの、またはより優れた実装を知っている場合は、それらについて言及してください。ここにはまだ理想的な実装はありません!

確実に高速な正規表現の実装はどこにありますか?

.NETまたはネイティブで.NETから合理的に使用できる、通常の非バックトラッキング(バックトラック)線形時間正規表現の実装を知っている人はいますか? System.Text.RegularExpressions有用であるためには、次のことが必要です。

• 正規表現の長さを m、入力の長さを n とすると、最悪の場合の正規表現評価の時間複雑度はO(m*n)になります。
• O(n) の通常の時間の複雑さを持ちます。これは、正規表現が実際に指数状態空間をトリガーすることはほとんどないか、可能であれば、入力のわずかなサブセットでのみトリガーするためです。
• 合理的な構築速度がある(つまり、潜在的に指数関数的な DFA がない)
• 数学者ではなく、人間が使用することを意図したものにする - たとえば、Unicode 文字クラスを再実装したくない: .NET または PCRE スタイルの文字クラスはプラスです。

ボーナスポイント：

• O（m）メモリではなくO（n + m）メモリを消費してネストを処理できるスタックベースの機能を実装する場合、実用性のボーナスポイント。
• 部分式または置換をキャプチャするためのボーナス ポイント(部分式の一致の可能性が指数関数的に存在する場合、それらすべてを列挙することは本質的に指数関数的ですが、最初のいくつかを列挙することはすべきではなく、置換についても同様です)。他の機能を使用することで、どちらかの機能が欠けていることを回避できるため、どちらかがあれば十分です。
• 正規表現をファーストクラスの値として扱うための多くのボーナスポイント（したがって、結合、交差、連結、否定を取ることができます-特に否定と交差は、正規表現定義の文字列操作によって行うのが非常に難しいため）
• 遅延マッチング、つまり、すべてをメモリに入れずに無制限のストリームでマッチングすることはプラスです。ストリームがシークをサポートしていない場合、部分式や置換をキャプチャすることは (一般に) 1 回のパスでは不可能です。
• 後方参照は outです。基本的に信頼できません。つまり、異常な入力ケースが与えられると、常に指数関数的な動作を示すことができます。

そのようなアルゴリズムは存在します (これは基本的なオートマトン理論です...) - しかし、.NET からアクセスできる実際に使用可能な実装はありますか?

背景: (これはスキップできます)

私は迅速で汚れたテキストのクリーンアップに Regex を使用するのが好きですが、perl/java/python/.NET で使用される一般的なバックトラッキング NFA 実装が指数関数的な動作を示すという問題に繰り返し遭遇しました。残念ながら、これらのケースは、正規表現の自動生成を開始するとすぐに、かなり簡単にトリガーされます。同じプレフィックスに一致する正規表現を交互に使用すると、指数関数的でないパフォーマンスでさえ非常に悪くなる可能性があります。たとえば、非常に基本的な例で、辞書を取得して正規表現に変換すると、ひどいパフォーマンスが予想されます。

より優れた実装が存在し、60 年代以降存在している理由の簡単な概要については、「正規表現の照合はシンプルかつ高速にできる」を参照してください。

あまり実用的ではないオプション:

• ほぼ理想的: FSA ツールキット。正規表現を DFA + NFA の高速な C 実装にコンパイルでき、変換器 (!) も許可され、交差とパラメーター化の構文を含むファーストクラスの正規表現 (カプセル化 yay!) があります。 しかし、それはプロローグです...（この種の実用的な機能を備えたものが主流の言語で利用できないのはなぜですか???）
• 高速ですが実用的ではありません: 優れたANTLRなどの完全なパーサーは、一般的に確実に高速な正規表現をサポートします。ただし、antlr の構文ははるかに冗長であり、もちろん、有効なパーサーを生成しない可能性のある構成を許可するため、安全なサブセットを見つける必要があります。

良い実装:

• RE2 - 適切な PCRE 互換性から後方参照を除外することを目的とした Google オープン ソース ライブラリ。作者によると、これは plan9 の正規表現 lib の unix ポートの後継だと思います。
• TRE - PCRE とほとんど互換性があり、逆参照も行いますが、それらを使用すると速度の保証が失われます。しかも超おまけマッチングモード搭載！

残念ながら、どちらの実装も C++ であり、.NET から使用するには相互運用が必要です。

1）次の効率を最小から最大に並べ替えます。 2^n, n!, n^5, 10000, nlog2(n)

私の答え->10000<nlog2（n）<n ^ 5 <2 ^ n <n！

正しい ？

2）アルゴの効率。このアルゴリズムのステップの場合、n^3です。1ナノ秒かかります。（10 ^ -9秒）。アルゴにはどれくらい時間がかかりますか。サイズ1000の入力を処理するには？

わからない…（1000）^ 3 * 10 ^ -9？

最近のインタビューで、技術的な質問の過程で出てきたさまざまなアルゴリズムの Big-O に関連するいくつかの質問をされました。私はこれについてあまりうまくやれなかったと思います...アルゴリズムのBig-Oを計算するように求められたプログラミングコースを受講してから10年間、私は何かの「Big-O」について一度も議論したことがありません手がけたり、デザインしたりしました。私は、コードの複雑さと速度について、他のチーム メンバーや一緒に働いたアーキテクトと多くの議論に参加してきましたが、実際のプロジェクトで Big-O 計算を実際に使用したチームの一員になったことはありません。議論は常に「アウトデータを理解した上で、これを行うためのより良い、またはより効率的な方法はありますか?」というものです。「このアルゴリズムの複雑さは何ですか」ということはありませんか?

人々が実際にコードの「Big-O」について実際に議論しているのかどうか疑問に思っていましたか?

問題を解決できません。誰かが私を助けることができますか？

以下のステートメントの Big O 表記法は何ですか:-