実際の使用では、 log(n)



は定数と見なすことができます。 一部の企業では、この定数があなたのものよりも大きいというだけです。 ©民俗の知恵

私の人生の半分はプログラムすることを学びます。 アルゴリズムの計算の複雑さをすばやく評価することを開発者に教えます。 なぜ？！

一見、これはかなりアカデミックなスキルであり、アルゴリズムテスト以外では必要ありません。 ただし、経験豊富な開発者は、itせずに反射レベルで毎日使用しています。 これは、読み取り、書き込み、または作成しようとしているコードの失礼な分析のために行われます。 通常、漸近性の迅速な分析は、非常に非効率的なコードの偶然の出現を排除するのに十分です。

最初に、短いが重要なタスクの例を使用して、複雑さを評価する方法を見つけましょう。 次に、明示的な評価を行う方法を学習する方法を説明し、JokerおよびDotNextカンファレンスの参加者がタスク例をどのように解決したかについての統計を示します。

写真はここからです 。

Joker 2017およびDotNext 2017 Moscowでの挑戦

昨年秋にモスクワで開催されたサンクトペテルブルクとドットネクストで行われたジョーカー会議に参加していた同僚から、コンタースタンドの複雑さについて何らかの問題を考え出すように頼まれました。

最初は、複雑さは退屈な悪いトピックであると判断しました。 しかし、それでも試してみることにしました。私の意見では、結果はかなり良かったです！ このアイデアは、家に帰る途中で簡単に生まれ、その後キーボードのほぼ1時間後ろで、短くても効果的なC＃コードの断片に整理しようとしました。 起こったことは次のとおりです。

 private static ISet<string> Compute(int n) { var set = new HashSet<string>(); for (int i = 2; i < n; i++) set.Add(ToBinaryString(i)); for (int step = 2; step < n; step++) for (int i = 2 * step; i < n; i += step) set.Remove(ToBinaryString(i)); return set; } private static string ToBinaryString(int x) { return x == 0 ? "0" : ToBinaryString(x / 2) + x % 2; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードを検討した結果、次の3つの質問に答えることが提案されました。

• この奇妙なコードは一般的に何をしますか？
• どうすれば最適化できますか？
• Compute(n)
  
  
  
  関数の複雑さは何ですか？

印象的なオプションのリストから最後の質問に対する最も正確な答えを選択することが提案されました。

• O（n）
• O（n²）
• O（n³）
• O（n log（n））
• O（nlog²（n））
• O（nlog³（n））
• O（n²log（n））
• O（n³log（n））
• O（n²log²（n））
• O（n²log³（n））
• O（n³log³（n））

ここで、コーヒーを注ぎ、コードの断片をもう一度読み、5分間推測して答えを選択します。 それからネタバレがあります。

解決策

ボトムアップから始めましょう。 ToBinaryStringメソッドの理解を容易にするもの-再帰的に動作して、文字列をバイナリレコードに変換します。 引数は再帰呼び出しごとに半分になるため、その深さはO(log(x))



です。 再帰の分岐がないため、この関数の複雑さはO(log(x))



であると判断して、ここで停止できO(log(x))



。

しかし、もう少し細心の注意を払い、C＃とJavaの文字列の不変性を思い出すことができます。 実際、文字列の連結はコピーにつながります。つまり、O（文字列の長さ）に対して機能します。 したがって、全体的な複雑さは対数よりもわずかに悪くなります。 O(log²(x))



が私たちの選択です！ もちろん、実用的な観点からは、違いはほとんど目立ちません（エピグラフを参照）が、パズルについては-それだけです！

Computeメソッドに戻ります。 最初のforループの複雑さはO(n log²(n))



です。 明らかに、メソッド全体の複雑さは、より重いネストされたものによって決まります。

内側のネストされたforループは、ToBinaryStringをO(n/step)



呼び出します。 したがって、合計の複雑さはO(n/2 + n/3 + n/4 +... n/(n-1)) = O(n(1/2 + 1/3 + ...))

ここで、括弧内の式が厳密に調和級数の部分和であることを覚えておくために、コンピューターサイエンスから数学分析に浅いダイビングをするときが来ました。 幸いなことに、このシリーズはさまざまな分野で研究されてきました。 特に、 オイラーの公式は、部分和がO(n log(n))



として増加することを示していO(n log(n))



。 ありがとう、分析、さようなら、さようなら、じゃあね！ :)

そのため、ToBinaryStringの呼び出しの価格を思い出して、上記のアルゴリズムの複雑さをO(n log³(n))



として評価できます。 これが答えです！

問題を解決することが判明しました、あなたは非常に多くを必要とします：

• 文字列の連結が悪いことを知っている
• 再帰的な方法の複雑さを考慮することができる
• HashSetのremoveは効率的に機能することを知っている
• ネストされたサイクルの複雑さの推定値をシリーズの部分和に減らすことができる
• そして最後に、調和級数の部分和のオイラー公式について知ること

わあ！ このような小さなコードではかなりクールなようです:)

何が起こっているの？

この奇妙なコードが一般的に何をするのか理解する時が来ましたか？ よく見てください！ 素数のリストの同じ検索- エラトステネスの未完成のふるいの方法による。 実際、内側のループは2番目ごと、3番目ごとなどを削除します。 その結果、1以外に分割されない人と自分自身だけが残ります。

適用される既知の最適化はありません（たとえば、ループの反復回数の合理的な選択）。ToBinaryStringの形式のペシミゼーションが完全に混乱するように追加されました。 その結果、元の複雑さO（n log（log（n）））およびトレースは残りませんでした。

会議参加者の興味深い最適化のヒントを次に示します。

• ToBinaryStringでメモ化を適用します。 簡単に言えば、結果をキャッシュします。 明らかに、これは物事をスピードアップしますが、これが複雑さの評価を改善することは全く明らかではありません。 そして本当に改善します。 いくらですか-自分で考えてください。
• HashSetではなく、BitArray（C＃）/ BitSet（Java）を使用します。 興味深いオファー。 これを行うには、行ではなく番号自体をセットに保存する必要があります。 また、ToBinaryStringメソッドは結果の最後にのみ適用する必要があります。 しかし、このリファクタリングだけで複雑さが改善されます。 その後、コレクションを置換すると、おそらく定数によってプログラムが高速化されますが、漸近的な複雑さの推定には影響しません:)
• 別の素数検索アルゴリズムを使用します。 たとえば、 AtkinふるいはO（n / log（log（n）））用です。

ジョーカーとメンバー DotNextメンバー

統計！

ジョーカーでは、86人がパズルを解きました。 これらのうち、8は正解O（nlog³（n））を与え、別の8は連結のトリックに該当し、O（nlog²（n））と答えました。

DotNextでは、69人がパズルを解きました。 これらのうち、10人が正解し、別の17人が回答O（nlog²（n））を返しました。 しかし、これらの統計によると、ジャビストに対するドナーの優位性に関する広範囲にわたるホリバーの結論を出すことはできません。 49人のコンターリストがDotNextに来て、彼らが有利だったことは確かです。

2時間の難易度評価コース

あなたは私がプログラムに教えることを忘れていませんか？

去年の秋、私はulearn.meを立ち上げました。これは、アルゴリズムの複雑さを明示的に評価するミニコースである「私たちの小さなカーソル」です。 わずか数時間で完了することができ、理論はほとんど含まれていませんが、単純な手法からより複雑な手法へと導く3ダースの問題を解決する必要があります。 このタスクの分析が理解しにくい場合、コースはあなたのためです。

おそらくこのコースは結果に影響を与えたのでしょう。 さらに、Jokerの後、このタスクの要素の分析を追加しました-良いように消えないように:)

エクスプレス評価の整理に2時間を費やしたい 内部のソーシャルネットワークで報酬を受け取らない ？ コースへようこそ。

ulearn.meの「 アルゴリズムの複雑さの推定 」