ماذا يعني التعقيد؟ ما هي صعوبة التعدين؟ باستخدام البيتكوين كمثال. O(n) - التعقيد الخطي

ما هي صعوبة التعدين؟ باستخدام البيتكوين كمثال.

يمكن أن يكون تعدين العملات المشفرة استثمارًا مربحًا للغاية. ولكن لكسب المال من تعدين العملات، يجب أن يكون لديك فهم جيد للفروق الدقيقة في الصناعة. من أهم المفاهيم لأي عامل تعدين هي صعوبة التعدين. الدخل يعتمد بشكل مباشر على صعوبة التعدين. توضح هذه المقالة بالتفصيل ماهية صعوبة التعدين وكيفية تشكيلها وما الذي يعتمد عليه.

ماذا يعني مصطلح "صعوبة التعدين"؟

تعدين العملات المشفرة عبارة عن عملية تتضمن إنشاء كتل جديدة من سلسلة blockchain وتسجيل المعاملات. يمكن مقارنة عمال المناجم بالمحاسبين الذين يعملون باستمرار على تحديث دفاترهم من خلال تسجيل جميع التحويلات. ولكن أي عمل يجب أن يدفع. يحصل عمال المناجم على مكافأة من النظام على شكل عملات معدنية للعملة المستخرجة.

إحدى ميزات العملات المشفرة هي طبيعتها الانكماشية. وهذا يعني أن العدد الإجمالي للعملات المعدنية المستخرجة لا يمكن أن يتجاوز العدد المحدد بواسطة رمز البرنامج. على سبيل المثال، الحد الأقصى لعدد عملات البيتكوين هو 21 مليون قطعة نقدية. علاوة على ذلك، سيتم استخراج آخر عملة بيتكوين فقط في عام 2140. على الرغم من عدد القائمين بالتعدين، يتم استخراج 12.5 بيتكوين فقط كل 10 دقائق. يتم توزيع هذه العملات بين القائمين بالتعدين وفقًا لقوة الحوسبة المنفقة. لا تزيد مكافأة الكتلة الموقعة (بل يتم تخفيضها بمقدار النصف كل 4 سنوات). وإذا زاد عدد عمال المناجم، فإن دخل كل عامل منجم سينخفض ​​بشكل متناسب. مع وصول المزيد والمزيد من القائمين بتعدين العملات المشفرة، تتزايد المنافسة على المكافآت المحدودة.

لتوضيح هذا الموقف بوضوح، تم تقديم معلمة محسوبة لـ "صعوبة التعدين" في شبكة العملة المشفرة. صعوبة التعدين هي مقياس يعكس مدى صعوبة حل مشكلة رياضية لتوقيع كتلة والحصول على مكافأة مقابلها. يتم إعادة حساب الصعوبة تلقائيًا بعد فترة زمنية معينة. الأمر مختلف بالنسبة لكل عملة مشفرة. على سبيل المثال، يتم إعادة حساب صعوبة تعدين البيتكوين كل كتل عام 2016، والتي يستغرق تعدينها حوالي أسبوعين. وفقًا لكود البرنامج، يتم ضبط الصعوبة بحيث يستغرق البحث عن الكتلة التالية حوالي 10 دقائق، بغض النظر عن عدد المعدنين وإجمالي معدل التجزئة.

وتزداد الصعوبة تلقائيًا إذا استغرق البحث عن آخر كتل 2016 أقل من أسبوعين. يشير هذا إلى أن إجمالي قوة الحوسبة لأجهزة التعدين قد زادت. على العكس من ذلك، ستكون الإشارة لتقليل التعقيد هي التباطؤ في البحث عن كتل 2016، نظرًا لانخفاض معدل التجزئة لجميع الأجهزة. والنتيجة هي رقابة مشددة على معدل إصدار العملات الجديدة.

أين تجد صعوبة التعدين. صعوبة تعدين أفضل 10 عملات مشفرة.

صعوبة التعدين هي مؤشر ديناميكي يتم إعادة حسابه بشكل دوري. مع زيادة القوة الحاسوبية لمعدات التعدين، يزداد التعقيد أيضًا. من الأفضل البحث عن معلومات محدثة عن حالة صعوبة تعدين العملة المشفرة على المواقع الرسمية للعملات. ومع ذلك، قد يكون هذا صعبا. يصعب أحيانًا العثور على روابط لإحصاءات التعدين حتى على المواقع الرسمية. لتبسيط العملية، تم إنشاء مواقع ويب لتجميع المعلومات الإحصائية حول جميع العملات المشفرة. إنهم يجمعون ويعالجون وينشرون البيانات الحالية ليس فقط حول صعوبة التعدين، ولكن أيضًا حول عشرات المؤشرات الأخرى: السعر، والرسملة، ومعدل التجزئة، والربحية، وعدد المعاملات، وما إلى ذلك.

يمكن العثور على معلومات محدثة عن أكثر من 100 عملة مشفرة على المواقع الإلكترونية التالية:

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

* يرجى ملاحظة أن صعوبة التعدين تتغير بمرور الوقت، لذلك قد توفر المواقع المختلفة بيانات صعوبة مختلفة. في بعض الأحيان يصل الفرق إلى 10-20% حسب العملة في مجمعين مختلفين. إذا كنت تبحث عن مؤشر لصعوبة التعدين ليس فقط لإرضاء فضولك، ولكن لأغراض عملية، فركز على الأرقام المتوسطة. على سبيل المثال، إذا كنت تقوم بالتنبؤ بالتغيرات في صعوبة التعدين في المستقبل بناءً على الديناميكيات التاريخية، فمن المنطقي أن تأخذ البيانات من الأشهر الستة الأخيرة إلى عام، بدلاً من أسبوعين إلى أربعة أسابيع.

** لا يمكن تعدين بعض العملات المشفرة بالمعنى التقليدي. يستخدم البعض تعدين نقاط البيع، حيث يتم تجميع الفائدة بشكل دوري على العملات المعدنية الموجودة في المحفظة. بالنسبة للتعدين عبر نقاط البيع، لا تحتاج إلى شراء معدات متخصصة أو إنفاق الأموال على الكهرباء. تم بالفعل استخراج العملات المشفرة الأخرى (على سبيل المثال، Ripple) بالكامل ويتم إعادة توزيعها فقط بين المالكين.

صعوبة التعدين: ما الذي يؤثر عليه ولماذا ينمو.

صعوبة التعدين تحدد دخل عامل المنجم. يتناسب عدد العملات المعدنية المستخرجة عكسيا مع صعوبة التعدين. إذا زادت صعوبة الشبكة بنسبة 20%، فسيتم تقليل دخل العملة المشفرة لكل عامل تعدين فردي بنسبة 20%.

على سبيل المثال، قامت ASIC لتعدين البيتكوين antminer s7 في منتصف عام 2017 (بشكل أكثر دقة، بصعوبة اعتبارًا من 1 يوليو 2017) بتعدين 0.06 بيتكوين شهريًا. لكن تعقيد شبكة البيتكوين يتزايد باستمرار. اعتبارًا من 1 نوفمبر 2017، ستنتج نفس المعدات بالفعل 0.026 بيتكوين شهريًا. انخفض دخل عامل المنجم بأكثر من النصف خلال 4 أشهر فقط.

لكن حتى الانخفاض الأسبوعي في الدخل لا يجعل استثمارات التعدين أقل جاذبية. يتم تعويض الإيرادات من العملات المشفرة جزئيًا من خلال الزيادة في سعر الصرف مقابل العملات الورقية. في مثالنا، في الأول من يوليو، كان سعر البيتكوين 2400 دولار، وفي 1 نوفمبر، ارتفعت الأسعار إلى ما يقرب من 6700 دولار. اتضح أن دخل عمال المناجم الورقية قد زاد على الرغم من الزيادة السريعة في تعقيد التعدين.

هذا هو منطق منشئي العملات المشفرة ذات التعقيد الديناميكي. وعلى الرغم من عدم وجود علاقة مباشرة بين سعر العملة ومدى صعوبة استخراجها، إلا أنه لا تزال هناك علاقة غير مباشرة. من المفترض أن الزيادة في التعقيد تعني زيادة في شعبية العملات المشفرة بين عامة السكان. أي شخص يتعلم عن العملات اللامركزية سيحاول تعدينها. سيؤدي هذا إلى زيادة التعقيد. ولكن في الوقت نفسه، من المرجح أن يرتفع الطلب، وبالتالي سعر الصرف. اتضح أن الاهتمام المتزايد بالمجتمع يحفز نمو سعر الصرف وزيادة تعقيد التعدين.

من الناحية الفنية، يعتمد مؤشر صعوبة التعدين على:

• معدل تجزئة الشبكة (عدد المعدات الخاصة بجميع عمال المناجم وقوتها الحاسوبية) ؛
• سرعة التعدين لعام 2016 كتل؛

وترتبط جميع المؤشرات الثلاثة بشكل مباشر. إن نمو معدل تجزئة الشبكة يعني انضمام مشاركين جدد إلى صناعة التعدين وزيادة المنافسة. ومع زيادة عدد المعدنين، يقل الوقت المستغرق في البحث عن الكتلة التالية. بعد كتلة 2016، يتم إعادة حساب صعوبة التعدين. يتم وصف التغيير في المؤشر بالنمط التالي:

صعوبة تعدين البيتكوين.

ترجع الزيادة في التعقيد إلى عدد من العوامل المترابطة بشكل وثيق:

• تطوير رقائق ASIC ودخول نماذج أكثر إنتاجية إلى السوق؛
• وتعميم عملة البيتكوين وتدفق عمال المناجم الجدد؛
• عائد مرتفع على الاستثمار في التعدين بسبب النمو السريع لسعر صرف البيتكوين مقابل الدولار؛
• نقل قوة الحوسبة من العملات الأخرى التي تنخفض أسعارها أو تنمو بشكل أبطأ من البيتكوين؛
• عوامل اخرى؛

زادت صعوبة تعدين البيتكوين بمقدار 5-6 مرات منذ عام 2016. واستمر النمو دون انقطاع تقريبًا. فقط في أغسطس 2017، ولأول مرة منذ عام، حدث انخفاض في المؤشر. ربما تأثر هذا بـ SegWit لشهر أغسطس الخاص بالبيتكوين، والذي أجبر بعض القائمين بالتعدين على نقل الطاقة إلى العملات البديلة.

6 إجابات

يتم تحديد التعقيد دائمًا بالنسبة لمتغير معين أو مجموعة من المتغيرات. لذلك عندما يتحدث المعيار عن إدخال وقت ثابت، فإننا نتحدث عن وقت ثابت بالنسبة لعدد العناصر في القائمة. أي أن إدراج O(1) يعني أن عدد العناصر الموجودة في القائمة لا يؤثر على التعقيد الإجمالي للإدراج. يمكن أن تحتوي القائمة على 500 أو 50000000 عنصر، وسيكون تعقيد عملية الإدراج هو نفسه.

على سبيل المثال، std::list تحتوي على عمليات إدراج وحذف O(1)؛ لا يعتمد عدد العناصر في القائمة على مدى تعقيد عمليات الإدراج. ومع ذلك، قد يعتمد تعقيد تخصيص الذاكرة على عدد الأشياء التي تم تخصيصها بالفعل. ولكن بما أن O(1) يتحدث عن عدد العناصر في القائمة، فهو لا يغطي ذلك. وهذا غير مفترض، لأننا حينها سنقيس مدى تعقيد مُخصص الذاكرة، وليس بنية البيانات.

باختصار: هذا بعد آخر.

هذا يعني أنه يمكننا تنفيذ الخوارزمية الخاصة بنا بالقوة التي نريدها، بما في ذلك الخوارزمية التي لا يكون فيها الوقت ثابتًا فعليًا بأي معنى عملي، ولكن حيث نحترم عدد "العمليات" على الكائنات المضمنة.

لم يتم تحديد التعقيد بالنسبة للتطبيقات. يتم تحديده بالنسبة للخوارزميات. لا يهم أن السياق يمكن أن يتغير لأن وقت التشغيل ليس مهمة صعبة.

كما هو مذكور أعلاه، يمكنك تنفيذ std::list باستخدام مخصص الذاكرة وهو O(log(n)) فيما يتعلق بعمليات الحذف (حيث n هو عدد التخصيصات). ومع ذلك، فإن حذف عنصر في القائمة سيظل O(1) فيما يتعلق بعدد العناصر في القائمة.

لا تخلط بين التعقيد والأداء العام. الهدف من التعقيد هو الحصول على مقياس مشترك للخوارزميات فيما يتعلق بالمتغيرات المختلفة. هدف المبرمج الذي يريد تشغيل التعليمات البرمجية الخاصة به بسرعة هو العثور على تطبيق معقول للخوارزمية يتوافق مع التعقيد المطلوب لتحقيق هذا الأداء.

التعقيد هو أداة لتقييم فعالية الخوارزمية. التعقيد لا يعني أنه يمكنك التوقف عن التفكير.

ماذا يعني بالضبط "الانخفاض"؟

كما أفهمها، التعقيد المستمر يعني أن العملية هي O(1): يمكنك معرفة عدد العمليات الذرية (القراءة/الكتابة، تعليمات التجميع، أيًا كان) التي سيتم تنفيذها مسبقًا. وهذا التقدير هو حد مشترك لجميع الحالات المحتملة للكائن المستهدف. هناك مشكلة هنا: في بيئة متعددة الخيوط، لا يمكنك التنبؤ بمفاتيح التدفق، لذلك يمكنك فقط القيام ببعض التفكير في وقت التشغيل المنقضي في نظام التشغيل في الوقت الفعلي.

فيما يتعلق بالتعقيد الثابت المطفأ، فهو أضعف. ومن خلال كتابة ملخص للإجابات، فإن ذلك يضمن استمرار العملية في المتوسط. وهذا يعني أن عدد العمليات الأولية للعمليات اللاحقة N هو O(N) . وهذا يعني أن عدد العمليات الأولية يبلغ حوالي O(1) ولكنه يسمح ببعض القفزات النادرة. على سبيل المثال، عادةً ما تكون إضافة عنصر إلى ذيل المتجه أمرًا دائمًا، ولكن في بعض الأحيان يلزم رفع أثقال إضافية؛ وجود وقت ثابت مستهلك يعني أن العملية الإضافية لا يتم تنفيذها كثيرًا وتستغرق وقتًا يمكن التنبؤ به، بحيث لا يزال إجمالي وقت العملية N هو O(N) . وبطبيعة الحال، نفس المصيد ينطبق هنا.

لذا، للإجابة على أسئلتك:

• تنطبق الضمانات المعقدة للمعيار في الواقع فقط على عدد تعليمات كود الآلة المطلوبة لتنفيذ عملية ما، ولا تعني أن وقت التنفيذ محدود بأي شكل من الأشكال. (في الواقع، حتى وقت قريب، لم يكن لدى C++ حتى مؤشر موضوع متعلق باللغة، لذلك من منظور C++ القياسي، بحلول هذا الوقت تم تنفيذ البرنامج على جهاز C++ متخصص.)
• الاستهلاك "يقتصر على ثابت في المتوسط"، والذي يحدث عادةً في حالة وقت تشغيل محدود ثابت دائمًا تقريبًا مع بعض الانحرافات النادرة إلى حد ما.

يحرر:
يمكنك الاطلاع، على سبيل المثال، على القسم 23.1 من معيار C++:

يتم تحديد جميع متطلبات التعقيد في هذا القسم فقط من حيث عدد العمليات على الكائنات المضمنة.

عندما يقال أن عملية ما لها "تعقيد مستمر"، فإنها عادة ما تشير في المقام الأول إلى التعقيد الزمني. يمكن أن أشير إلى التعقيد المكاني، ولكن إذا كان الأمر كذلك، فسيتم ذكره صراحةً كالمعتاد.

الآن، يشير تعقيد العملية إلى مقدار الوقت الذي ستستغرقه العملية لإكمالها عندما يزيد عدد العناصر التي تتم معالجتها في العملية. بالنسبة لعملية التعقيد المستمرة، ستستغرق الوظيفة نفس القدر من الوقت سواء تمت معالجة صفر عنصر أو عشرة ملايين عنصر.

المبادلة () هي تعقيد مستمر لأنه بغض النظر عن عدد العناصر الموجودة في المتجه، فإن العملية ستستغرق نفس القدر من الوقت.

انقر على القائمة. هو تعقيد مستمر لأنه على الرغم من أن تخصيص عنصر جديد قد يستغرق بعض الوقت، إلا أن وقت التخصيص هذا لا يزيد لأن القائمة تحتوي على 10 ملايين عنصر (على الأقل ليس بالمعنى الخوارزمي - بالطبع، إذا أصبحت الذاكرة الحرة أكبر وأكثر استنفادًا، قد يستغرق التخصيص وقتًا أطول، ولكن من وجهة نظر خوارزمية، هناك كمية لا حصر لها من الذاكرة).

يسمى Push_back() على المتجه بالثابت "المستهلك" لأنه في الحالة العادية، عندما لا تحدث إعادة التخصيص، فإن مقدار الوقت الذي ستستغرقه العملية لا يرتبط بعدد العناصر الموجودة في المتجه بالفعل - نفس المقدار من يستغرق الوقت لإضافة عنصر واحد جديد إلى متجه الطول صفر بالنسبة إلى متجه الطول 10 ملايين. ومع ذلك، إذا كان المتجه يحتاج إلى إعادة تخصيص، فسيكون من الضروري الحصول على نسخة من العناصر الموجودة، وهذه ليست عملية ثابتة - إنها عملية خطية. لكن من المفترض أن يتم تصميم المتجه بطريقة تجعل عمليات إعادة التخصيص تحدث بشكل غير متكرر، بحيث يمكن استهلاكها عبر العديد من عمليات Push_back().

لكن إجراء عملية الدفع للخلف على المتجه أمر لا يمكن التنبؤ به. سيكون هذا سريعًا جدًا في معظم الأوقات، ولكن بين الحين والآخر سيتعين عليه إعادة تخصيص المساحة لجميع البيانات ونسخ كل عنصر إلى موقع جديد. لذا، فهي أقل قابلية للتنبؤ بها من حيث وقت التنفيذ من القائمة::push_front وحدها، لكنها لا تزال تسمى مستمرة (مطفأة). في المتوسط، ستتطلب إضافة كمية كبيرة من البيانات إلى المتجه تعقيدًا مستقلاً عن الكمية المضافة، ولهذا السبب يطلق عليه الوقت "الثابت المطفأ". (يمين؟)

التعقيد هو O(1) - الثابت (مع مراعاة التعقيد الزمني) يعني أن وقت إكمال الخوارزمية لا يرتبط بحجم المشكلة.

لذا، فإن البحث عن قيمة في بنية مجزأة هو O(1) لأن الوقت المستغرق للقيام بذلك لا يعتمد على عدد قيمها. ومع ذلك، لا ينطبق الأمر نفسه على القائمة المرتبطة لأنه يتعين علينا فحص القيم (التي يتغير عددها مع زيادة عدد العناصر) للعثور على قيمتها.

في الحالة 3، عندما تقوم بنسخ كل عنصر، فهي ليست عملية O(1)، ولكنها عملية O(N) (لكنها في معظم الأحيان تكون O(1)، لذا فهي عادة ثابتة). يأخذ الاستهلاك ذلك في الاعتبار من خلال ملاحظة أن الخوارزمية تكتمل عادةً في وقت O(1) ونادرًا ما تقع في حالة O(N) هذه.

من المحتمل أنك صادفت رموزًا مثل O(log n) أكثر من مرة أو سمعت عبارات مثل "التعقيد الحسابي اللوغاريتمي" موجهة إلى بعض الخوارزميات. وإذا كنت لا تزال لا تفهم ما يعنيه هذا، فهذا المقال لك.

تصنيف الصعوبة

عادة ما يتم قياس مدى تعقيد الخوارزميات من خلال وقت تنفيذها أو استخدام الذاكرة. في كلتا الحالتين، يعتمد التعقيد على حجم البيانات المدخلة: ستتم معالجة مجموعة مكونة من 100 عنصر بشكل أسرع من مجموعة مماثلة مكونة من 1000 عنصر. ومع ذلك، يهتم عدد قليل من الأشخاص بالوقت المحدد: يعتمد ذلك على المعالج ونوع البيانات ولغة البرمجة والعديد من المعلمات الأخرى. فقط التعقيد المقارب هو المهم، أي التعقيد عندما يميل حجم البيانات المدخلة إلى ما لا نهاية.

لنفترض أن بعض الخوارزميات تحتاج إلى إجراء عمليات شرطية 4n 3 + 7n لمعالجة عناصر n من بيانات الإدخال. مع زيادة n، سيتأثر وقت التشغيل النهائي بشكل ملحوظ برفع n إلى مكعب بدلاً من ضربه في 4 أو إضافة 7n. ثم يقولون أن التعقيد الزمني لهذه الخوارزمية هو O(n 3)، أي أنه يعتمد بشكل مكعب على حجم البيانات المدخلة.

يأتي استخدام الحرف الكبير O (أو ما يسمى بتدوين O) من الرياضيات، حيث يتم استخدامه لمقارنة السلوك المقارب للوظائف. رسميًا، O(f(n)) يعني أن وقت تشغيل الخوارزمية (أو مقدار الذاكرة المشغولة) ينمو اعتمادًا على حجم بيانات الإدخال ليس أسرع من بعض الثابت مضروبًا في f(n) .

أمثلة

O(n) - التعقيد الخطي

على سبيل المثال، تتميز خوارزمية البحث عن العنصر الأكبر في مصفوفة غير مصنفة بهذا التعقيد. سيتعين علينا مراجعة جميع عناصر المصفوفة n لفهم أي منها هو الحد الأقصى.

O(log n) - التعقيد اللوغاريتمي

أبسط مثال هو البحث الثنائي. إذا تم فرز المصفوفة، فيمكننا التحقق مما إذا كانت تحتوي على قيمة معينة باستخدام طريقة النصف. دعونا نتحقق من العنصر الأوسط، إذا كان أكبر من العنصر الذي نبحث عنه، فسوف نتجاهل النصف الثاني من المصفوفة - فهو بالتأكيد ليس هناك. إذا كان أقل، ثم على العكس من ذلك - سوف نتخلص من النصف الأولي. وهكذا سنستمر في التقسيم إلى نصفين، وفي النهاية سوف نتحقق من عناصر السجل n.

O(ن 2) - التعقيد التربيعي

على سبيل المثال، خوارزمية فرز الإدراج لديها هذا التعقيد. في التنفيذ الأساسي، يتكون من حلقتين متداخلتين: واحدة للمرور عبر المصفوفة بأكملها، والثانية للعثور على مكان العنصر التالي في الجزء الذي تم فرزه بالفعل. وبالتالي، فإن عدد العمليات سيعتمد على حجم المصفوفة مثل n * n، أي n 2.

هناك تصنيفات أخرى للصعوبة، لكنها جميعها تقوم على نفس المبدأ.

ويحدث أيضًا أن وقت تشغيل الخوارزمية لا يعتمد على الإطلاق على حجم البيانات المدخلة. ثم يُشار إلى التعقيد بـ O(1) . على سبيل المثال، لتحديد قيمة العنصر الثالث في المصفوفة، لا تحتاج إلى تذكر العناصر أو المرور عليها عدة مرات. كل ما عليك فعله دائمًا هو انتظار العنصر الثالث في دفق بيانات الإدخال وستكون هذه هي النتيجة، والتي تستغرق نفس الوقت لحساب أي كمية من البيانات.

وينطبق الشيء نفسه على تقييمات الذاكرة عندما يكون ذلك مهمًا. ومع ذلك، يمكن للخوارزميات استخدام ذاكرة أكبر بشكل ملحوظ عند زيادة حجم البيانات المدخلة مقارنة بالخوارزميات الأخرى، ولكنها لا تزال تعمل بشكل أسرع. والعكس صحيح. ويساعد ذلك على اختيار أفضل الطرق لحل المشكلات بناءً على الظروف والمتطلبات الحالية.