問題タブ [complexity-theory]

CS の学位を取得したほとんどの人は、 Big O の略語を知っているはずです。アルゴリズムがどれだけうまくスケールするかを測定するのに役立ちます。

しかし、興味深いのは、アルゴリズムの複雑さをどのように計算または概算するのですか?

私はこれに対する答えをどこにも得られませんでした。正規表現の一致と置換の実行時の複雑さはどれくらいですか？

編集：私はPythonで作業しています。しかし、最も人気のある言語/ツール（java、perl、sed）について一般的に知りたいです。

Pythonソースコードを自分で調べてオブジェクトがどのように機能するかを判断する以外に、この情報のソースを見つけることができませんでした。私がこれをオンラインで見つけることができる場所を誰かが知っていますか？

Web開発のために既存のフレームワークに切り替えることはどの程度の複雑さで必須ですか？

Web開発では、どのような複雑さの測定が実用的ですか？コードの長さ？機能リスト？データベースサイズ？

多くの場合、私たちは問題に取り組んでいることに気づき、作成されたソリューションが問題が必要とするよりもはるかに複雑であることを理解するだけです. 職場での合併症を制御するのに役立つコントロール、ベスト プラクティス、テクニックなどはありますか?

P=NP かどうかという問題は、おそらくすべてのコンピューター サイエンスで最も有名です。どういう意味ですか？そして、なぜそれはとても興味深いのですか？

ああ、そして追加の信用のために、声明の真実または虚偽の証拠を投稿してください. :)

私は計算複雑性のコースを受講していますが、これまでのところ、開発者にとってあまり役に立たないという印象を受けました。

私が間違っているかもしれませんが、以前にこの道をたどったことがある場合は、複雑性理論があなたの仕事にどのように役立ったかの例を教えてください。たくさんの感謝。

配列、リンクされたリスト、ハッシュ テーブルなどを含む最も一般的なデータ構造に対する操作の Big O 表記の概要はありません。

ビッグオー記法とは？使いますか？

私はこの大学のクラスを逃したと思います:D

誰かがそれを使用し、それを使用した場所の実例を挙げていますか?

以下も参照してください。

8歳のビッグオー？
Big O さん、どのように計算/概算しますか?
計算複雑性理論を実生活に適用しましたか?

私は通常、特定の型の値 (文字列やその他のオブジェクトなどのキー値) に関連付けられたデータを格納する必要があるときはいつでも、C++ stdlib マップを使用します。stdlib マップの実装は、標準の配列または stdlib ベクトルよりも優れたパフォーマンス (O(log n)) を提供するツリーに基づいています。

私の質問は、さらに優れたパフォーマンス (O(1)) を提供する C++ の「標準」ハッシュテーブル実装を知っていますか? Java API の Hashtable クラスで利用できるものに似たもの。