コードの時間と空間の複雑さを知る/近似する最も良い方法は何ですか？

Question

それは私には特に分かりません。 もちろん、あなたのコードが毎回リストのn個の要素を反復するだけなら、私たちはO（n）時間を見ています。しかし、組み込みの関数はどうでしょうか？私はPython（と一般的なコーディング）には新しくてスーパーです。だから、ある関数が要素を反復処理しなければならないのか、それとも何らかの形で、必要な要素をハッシュテーブルのようにすぐに引き出すことができるかどうかを、どのように知っていますか？ >。> ... たとえば、最初にリストを更新するたびに、新しいリスト全体が実際に作成され、再投入されることはわかりませんでした。それは前にしたと思ったように、要素を裏側に押し当てるよりもはるかに多くのステップです。\ それでは、何か他のことは何もしていないのですか？ X.x

Answer 1

悲しいことに、これは簡単には答えがありません。よく書かれたコードには、各メソッドの実行時間を示すコメントが付いていますが、必ずしもそうであるとは限りません。他の誰かが書いたメソッドを使用していて、メソッドのランタイムを文書化していない場合、唯一のオプションはコードを見てそれを把握することです。

より多くの経験をすると、関数の複雑さを推測するのが簡単になります。これは、使用されているデータ構造と呼び出し元のコードが何をしなければならないかを知ることから来ています。