複雑とはどういう意味ですか? 採掘難易度とは何ですか？ 例としてビットコインを使用します。 O(n) - 線形複雑度

採掘難易度とは何ですか？ 例としてビットコインを使用します。

暗号通貨マイニングは非常に収益性の高い投資となる可能性があります。 しかし、通貨マイニングで利益を得るには、業界の微妙な違いをよく理解する必要があります。 マイナーにとって最も重要な概念の 1 つは、マイニングの難しさです。 収入は採掘の難易度に直接依存します。 この記事では、マイニング難易度とは何か、それがどのように形成されるか、そしてそれが何に依存するのかについて詳しく説明します。

「採掘難易度」とは何を意味しますか?

暗号通貨マイニングは、ブロックチェーン チェーンの新しいブロックの生成とトランザクションの記録を含むプロセスです。 マイナーは、すべての送金を記録することで帳簿を最新の状態に保つために常に努力する会計士にたとえることができます。 しかし、どんな仕事でも報酬は支払わなければなりません。 マイナーは、採掘された通貨のコインの形でシステムから報酬を受け取ります。

仮想通貨の特徴の一つはデフレ性です。 これは、採掘されたコインの総数がプログラム コードで指定された数を超えることができないことを意味します。 たとえば、ビットコインの最大数は 2,100 万コインです。 さらに、最後のビットコインは 2140 年にのみ採掘される予定です。 マイナーの数にもかかわらず、10 分ごとに採掘されるのはわずか 12.5 BTC です。 これらのコインは、消費された計算能力に応じてマイナーに分配されます。 署名されたブロックの報酬は増加しません (さらには 4 年ごとに半分に減ります)。 そして、マイナーの数が増加すると、各マイナーの収入は比例して減少します。 ますます多くの新しい仮想通貨マイナーの登場により、限られた報酬をめぐる競争が激化しています。

この状況を明確に示すために、仮想通貨ネットワークの計算パラメータ「マイニング難易度」が導入されました。 マイニングの難易度は、ブロックに署名して報酬を受け取るための数学的問題を解決することがどれほど難しいかを反映する指標です。 難易度は一定時間が経過すると自動で再計算されます。 仮想通貨ごとに異なります。 たとえば、ビットコインのマイニングの難易度は 2016 ブロックごとに再計算され、マイニングには約 2 週間かかります。 プログラムコードによれば、マイナー数や総ハッシュレートに関わらず、次のブロックの検索に10分程度かかるように難易度が調整されています。

最後の 2016 ブロックの検索にかかった時間が 2 週間未満の場合、難易度は自動的に上がります。 これは、マイニング デバイスの総コンピューティング能力が向上したことを示唆しています。 逆に、すべてのデバイスのハッシュレートが低下しているため、複雑さを軽減するシグナルは、2016 ブロックの検索の速度低下となります。 その結果、新しいコインの発行レートが厳密に制御されます。

採掘の難易度を見つける場所。 トップ 10 の仮想通貨のマイニングの難しさ。

マイニングの難易度は、定期的に再計算される動的な指標です。 マイニング機器の計算能力が増加するにつれて、複雑さも増加します。 仮想通貨のマイニングの難易度に関する最新情報は、通貨の公式ウェブサイトで探すのが最善です。 ただし、これは難しい場合があります。 マイニング統計へのリンクは、公式 Web サイトであっても見つけるのが難しい場合があります。 プロセスを簡素化するために、すべての暗号通貨に関する統計情報を集約する Web サイトが作成されました。 彼らは、マイニングの難易度だけでなく、価格、資本化、ハッシュレート、収益性、トランザクション数などの他の数十の指標に関する現在のデータを収集、処理、公開しています。

100 を超える暗号通貨に関する最新情報は、次の Web サイトでご覧いただけます。

• https://www.coinwarz.com/charts/difficulty-charts
• https://bitinfocharts.com/ru/

* マイニングの難易度は時間の経過とともに変化するため、サイトごとに異なる難易度のデータが提供される場合があることに注意してください。 2 つの異なるアグリゲーターでは、通貨ごとにその差が 10 ～ 20% に達する場合があります。 好奇心を満たすだけでなく実用的な目的でマイニングの難易度を示す指標を探している場合は、平均値に注目してください。 たとえば、過去の動向に基づいて将来の採掘難易度の変化を予測する場合は、2 ～ 4 週間ではなく、過去 6 か月から 1 年分のデータを取得する方が合理的です。

** 一部の暗号通貨は従来の意味ではマイニングできません。 ウォレット内のコインに定期的に利子が発生する POS マイニングを使用するものもあります。 POS マイニングの場合、専用の機器を購入したり、電気代を費やす必要はありません。 他の暗号通貨 (リップルなど) はすでに完全にマイニングされており、所有者間でのみ再配布されます。

マイニングの難易度: それがどのような影響を及ぼし、なぜ成長しているのか。

マイニングの難易度によってマイナーの収入が決まります。 採掘されるコインの数は採掘の難易度に反比例します。 ネットワークの難易度が 20% 増加すると、個々のマイナーの仮想通貨収入は 20% 減少します。

たとえば、2017 年半ばのビットコイン マイニング アントマイナー s7 の ASIC (より正確には、2017 年 7 月 1 日時点では困難が伴いました) は、月あたり 0.06 BTC をマイニングしました。 しかし、ビットコインネットワークの複雑さは継続的に増加しています。 2017 年 11 月 1 日の時点で、同じ装置はすでに月あたり 0.026 BTC を生産しています。 鉱山労働者の収入はわずか 4 か月で半分以下に減少しました。

しかし、たとえ毎週の収入が減少したとしても、鉱山投資の魅力が損なわれるわけではありません。 暗号通貨の収益は、法定通貨への為替レートの上昇によって部分的に相殺されます。 この例では、7 月 1 日のビットコイン レートは 2,400 ドルでしたが、11 月 1 日には相場はほぼ 6,700 ドルまで上昇しました。 マイニングの複雑さが急速に増大しているにもかかわらず、法定通貨マイナーの収入は増加していることが判明しました。

これは、動的に複雑な暗号通貨の作成者のロジックです。 通貨の価格とマイニングの難易度の間には直接的な関係はありませんが、間接的な関係は依然として存在します。 複雑さの増加は、一般人口の間での暗号通貨の人気の増加を意味すると考えられます。 分散型通貨について学んだ人はマイニングを試みるでしょう。 これにより、複雑さが増します。 しかし同時に、需要が増加する可能性が高く、したがって為替レートも上昇します。 社会への関心の高まりが、為替レートの成長とマイニングの複雑さの増大の両方を刺激していることがわかりました。

技術的な観点から見ると、マイニング難易度の指標は以下によって決まります。

• ネットワークハッシュレート（すべてのマイナーの機器の数と計算能力）。
• 2016 ブロックのマイニング速度。

3 つの指標はすべて直接関連しています。 ネットワークのハッシュレートの上昇は、採掘業界に新たな参加者が加わり、競争が激化していることを意味します。 マイナーの数が増えると、次のブロックの検索にかかる時間が減少します。 2016 ブロック以降、マイニング難易度は再計算されます。 インジケーターの変化は次のパターンで表されます。

ビットコインのマイニングの難易度。

複雑さの増加は、密接に相互に関連するいくつかの要因によるものです。

• ASICチップの開発と、より生産性の高いモデルの市場への参入。
• ビットコインの普及と新たなマイナーの流入。
• ビットコインの対ドル為替レートの急成長によるマイニングへの高い投資収益率。
• 相場がビットコインよりも下落または上昇している他の通貨からのコンピューティング能力の移転。
• その他の要因。

ビットコインのマイニングの難易度は2016年以来5〜6倍に増加しています。 成長はほぼ途切れることなく続いた。 2017年8月にのみ、1年ぶりに指標が減少しました。 おそらくこれは、一部のマイナーが権力をアルトコインに移管することを余儀なくされた、ビットコインの 8 月の SegWit の影響を受けたものと思われます。

6 件の回答

複雑さは常に、特定の変数または変数のセットに関連して指定されます。 したがって、標準が定数時間の挿入について語るとき、それはリスト内の要素の数に対する定数時間について話していることになります。 つまり、O(1) 挿入は、リスト内に存在する要素の数が挿入の全体的な複雑さに影響を与えないことを意味します。 リストには 500 個または 50000000 個の要素を含めることができ、挿入操作の複雑さは同じになります。

たとえば、std::list には O(1) 個の挿入と削除があります。 リスト内の要素の数は、挿入の複雑さには依存しません。 ただし、メモリ割り当ての複雑さは、すでに割り当てられているものの数に依存する場合があります。 ただし、O(1) ではリスト内の要素の数について説明しているため、それについては説明していません。 そして、これは想定されていません。なぜなら、データ構造ではなくメモリ アロケータの複雑さを測定することになるからです。

一言で言えば、これは別の次元です。

これは、実用的な意味で時間は実際には一定ではないものの、含まれるオブジェクトに対する「操作」の数を考慮した場合など、アルゴリズムを好きなだけ強力に実装できることを意味します。

複雑さは実装に関連して指定されません。 アルゴリズムに関連して指定されます。 ランタイムは難しいタスクではないため、コンテキストが切り替わることは問題ではありません。

上記のように、削除に関して O(log(n)) のメモリ アロケータを使用して std::list を実装できます (n は割り当ての数です)。 ただし、リスト内の要素を削除しても、リスト内の要素の数に関しては O(1) になります。

複雑さと全体的なパフォーマンスを混同しないでください。 複雑さの目標は、さまざまな変数に関するアルゴリズムに共通のメトリックを持たせることです。 コードを高速に実行したいプログラマーの目標は、そのパフォーマンスを達成するために必要な複雑さに見合ったアルゴリズムの合理的な実装を見つけることです。

複雑さは、アルゴリズムの有効性を評価するためのツールです。 複雑だからといって、考えるのをやめてよいというわけではありません。

「減価償却」とは具体的に何を意味するのでしょうか？

私が理解しているところによると、一定の複雑さは操作が O(1) であることを意味します。実行されるアトミック操作 (読み取り/書き込み、アセンブリ命令など) の数が事前にわかります。 そして、この推定値は、ターゲット オブジェクトのすべての可能な状態の共通の境界になります。 ここには落とし穴があります。マルチスレッド環境ではフローの切り替えを予測できないため、リアルタイム OS では経過した実行時間から推論するしかありません。

償却定数の複雑さについては、さらに弱いです。 回答の概要を書き込むことで、平均して業務が確実に継続するようになります。 これは、N 個の後続の操作に対する基本操作の数が O(N) であることを意味します。 これは、基本的な演算の数は約 O(1) ですが、まれにジャンプが発生することは許容されることを意味します。 たとえば、要素をベクトルの末尾に追加すると、通常は永続的ですが、追加の重労働が必要になる場合があります。 償却定数があるということは、追加の演算がそれほど頻繁には実行されず、予測可能な時間がかかるため、演算 N の合計時間は依然として O(N) であることを意味します。 もちろん、ここでも同じ問題が当てはまります。

したがって、あなたの質問に答えるには:

• この標準の複雑な保証は、実際には操作の実行に必要なマシンコード命令の数にのみ適用され、実行時間がいかなる形でも制限されることを意味するものではありません。 (実際、最近まで C++ には言語関連のトピック ポインターさえありませんでした。そのため、標準の C++ の観点から見ると、この時点ではプログラムは特殊な C++ マシンで実行されていました。)
• 減価償却費は「平均して一定に制限される」もので、これは通常、ほとんど常に一定の制限された稼働時間の場合に発生しますが、かなりまれな偏差は発生します。

編集：
たとえば、C++ 標準のセクション 23.1 を参照してください。

このセクションのすべての複雑さの要件は、含まれるオブジェクトに対する操作の数のみに関して指定されます。

操作が「一定の複雑さ」を持つと言われるとき、それは通常、主に時間の複雑さを指します。 空間の複雑さについて言及している可能性もありますが、その場合は、それが正常であると明示的に述べられるでしょう。

ここで、操作の複雑さとは、操作で処理される要素の数が増加した場合に、操作が完了するまでにどれだけ時間がかかるかを指します。 一定の複雑さの操作の場合、処理される項目がゼロであっても、1,000 万項目であっても、関数にかかる時間は同じになります。

swap() は、ベクトル内の要素の数に関係なく、操作にかかる時間は同じであるため、複雑さは一定です。

リストをクリックします。 新しい要素を割り当てるにはある程度の時間がかかる場合がありますが、リストには 1,000 万個の要素が含まれているため、この割り当て時間は増加しません (少なくともアルゴリズム的な意味では - もちろん、空きメモリが大きくなった場合) ため、複雑さは一定です。メモリがさらに枯渇すると、割り当てに時間がかかることがありますが、アルゴリズムの観点からは、メモリの量は無限です)。

ベクトルの Push_back() は、「償却」定数と呼ばれます。これは、通常の場合、再割り当てが発生しない場合、操作にかかる時間は、ベクトル内に既に存在する要素の数に関係なく、同じ量であるためです。長さ 1000 万のベクトルに対して長さ 0 のベクトルに新しい要素を 1 つ追加するには時間がかかります。 ただし、ベクトルを再割り当てする必要がある場合は、既存の要素のコピーが必要になります。これは一定の操作ではなく、線形操作です。 ただし、ベクトルは、再割り当てが頻繁に発生しないように設計されているため、多くの Push_back() 操作で償却できるようにする必要があります。

しかし、ベクトルに対して Push_back を実行することはさらに予測不可能です。 ほとんどの場合、これは非常に高速ですが、場合によっては、すべてのデータのスペースを再割り当てし、各要素を新しい場所にコピーする必要があります。 したがって、 list::push_front 単独よりも実行時間の予測可能性は低くなりますが、それでも永続的 (償却される) と呼ばれます。 平均して、大量のデータをベクトルに追加すると、追加される量とは無関係に複雑さが発生します。そのため、「償却定数」時間と呼ばれます。 （右？）

複雑度は O(1) - 定数 (時間計算量を考慮) は、アルゴリズムの完了時間が問題のサイズに関係しないことを意味します。

したがって、ハッシュ構造内の値の検索にかかる時間は値の数に依存しないため、O(1) になります。 ただし、リンクされたリストには同じことが当てはまりません。値を見つけるために値 (要素数が増加するにつれて値の数が変化します) をスキャンする必要があるからです。

ケース 3 では、各要素をコピーするとき、O(1) 操作ではなく、O(N) 操作になります (ただし、ほとんどの場合は O(1) なので、通常は定数です)。 償却では、アルゴリズムは通常 O(1) 時間で完了し、この O(N) のケースに陥ることはほとんどないことに注意して、これを考慮します。

おそらく、O(log n) のような表記法に何度も遭遇したり、一部のアルゴリズムを対象とした「対数計算量」のようなフレーズを聞いたことがあるでしょう。 これが何を意味するのかまだ理解できない場合は、この記事を読んでください。

難易度評価

アルゴリズムの複雑さは通常、実行時間またはメモリ使用量によって測定されます。 どちらの場合も、複雑さは入力データのサイズに依存します。つまり、100 要素の配列は、同様の 1000 要素の配列よりも高速に処理されます。ただし、正確な時間に興味がある人はほとんどいません。プロセッサやデータ型によって異なります。 、プログラミング言語、その他多くのパラメータ。 漸近的な複雑さ、つまり入力データのサイズが無限大になる傾向がある場合の複雑さだけが重要です。

あるアルゴリズムが、入力データの n 要素を処理するために 4n 3 + 7n の条件付き演算を実行する必要があるとします。 n が増加するにつれて、最終的な動作時間は、n を 4 倍したり 7n を加算したりするよりも、n を 3 乗することによって大幅に影響を受けます。 そして、このアルゴリズムの時間計算量は O(n 3) である、つまり、入力データのサイズに 3 次的に依存すると彼らは言います。

大文字の O (またはいわゆる O 表記法) の使用は数学に由来しており、関数の漸近的な動作を比較するために使用されます。 正式には、 O(f(n)) は、アルゴリズムの実行時間 (または占有されるメモリの量) が、入力データのサイズに応じて、ある定数を f(n) で乗算した速度より速く増加しないことを意味します。

例

O(n) - 線形複雑度

たとえば、ソートされていない配列内の最大の要素を見つけるアルゴリズムには、このような複雑さが伴います。 どれが最大であるかを理解するには、配列の n 個の要素をすべて調べる必要があります。

O(log n) - 対数複雑度

最も単純な例は二分探索です。 配列がソートされている場合は、半分にする方法を使用して、配列に特定の値が含まれているかどうかを確認できます。 中央の要素をチェックしてみましょう。それが探している要素より大きい場合は、配列の後半を破棄します。間違いなくそこにはありません。 それが小さい場合はその逆です。最初の半分は破棄されます。 そして、引き続き半分に分割し、最終的に log n 個の要素を確認します。

O(n 2) - 二次複雑度

たとえば、挿入ソート アルゴリズムにはこのような複雑さがあります。 正規の実装では、これは 2 つのネストされたループで構成されます。1 つは配列全体を処理するループ、もう 1 つはソート済みの部分で次の要素の場所を見つけるループです。 したがって、演算数は配列のサイズ n * n、つまり n 2 に依存します。

他にも難易度の評価がありますが、それらはすべて同じ原則に基づいています。

また、アルゴリズムの実行時間が入力データのサイズにまったく依存しないこともあります。 この場合、複雑度は O(1) として表されます。 たとえば、配列の 3 番目の要素の値を決定するために、要素を覚えたり、要素を何度も調べたりする必要はありません。 常に入力データ ストリームの 3 番目の要素を待つだけで結果が得られ、データ量に関係なく計算にかかる時間は同じになります。

重要な場合の記憶評価にも同じことが当てはまります。 ただし、入力データのサイズを増やすと、アルゴリズムは他のアルゴリズムよりも大幅に多くのメモリを使用する可能性がありますが、それでも高速に実行されます。 およびその逆。 これは、現在の状況と要件に基づいて問題を解決する最適な方法を選択するのに役立ちます。