Какво означава сложност? Какво представлява трудността при копаене? Използване на биткойн като пример. O(n) - линейна сложност

Какво представлява трудността при копаене? Използване на биткойн като пример.

Добивът на криптовалута може да бъде много печеливша инвестиция. Но за да правите пари от копаене на валута, трябва да имате добро разбиране на нюансите на индустрията. Една от най-важните концепции за всеки миньор е трудността на копаене. Доходите пряко зависят от трудността на добива. Тази статия описва подробно каква е трудността при копаене, как се формира и от какво зависи.

Какво означава терминът „трудност при копаене“?

Добивът на криптовалута е процес, който включва генериране на нови блокове от блокчейн веригата и записване на транзакции. Миньорите могат да бъдат сравнени със счетоводители, които постоянно работят, за да поддържат своите книги актуални, като записват всички трансфери. Но всяка работа трябва да бъде платена. Копачите получават награда от системата под формата на монети от добитата валута.

Една от характеристиките на криптовалутите е тяхната дефлационна природа. Това означава, че общият брой изкопани монети не може да надвишава броя, определен от програмния код. Например, максималният брой биткойни е 21 милиона монети. Освен това последният биткойн ще бъде добиван едва през 2140 г. Въпреки броя на копачите, само 12,5 BTC се добиват на всеки 10 минути. Тези монети се разпределят между миньорите според изразходваната изчислителна мощност. Наградата за подписан блок не се увеличава (и дори се намалява наполовина на всеки 4 години). И ако броят на миньорите се увеличи, тогава доходът на всеки отделен миньор намалява пропорционално. С пристигането на все повече и повече нови крипто копачи, конкуренцията за ограничени награди нараства.

За да се демонстрира ясно тази ситуация, беше въведен изчислен параметър на мрежата за криптовалута „трудност при копаене“. Трудността при копаене е метрика, която отразява колко трудно е да се реши математическата задача, за да се подпише блок и да се получи награда за това. Трудността се преизчислява автоматично след определен период от време. За всяка криптовалута е различно. Например, трудността на копаене на биткойни се преизчислява на всеки 2016 блока, чието копаене отнема приблизително 2 седмици. Според програмния код, трудността се регулира така, че търсенето на следващия блок да отнема приблизително 10 минути, независимо от броя на копачите и общия хешрейт.

Трудността се увеличава автоматично, ако търсенето на последните 2016 блока отне по-малко от две седмици. Това предполага, че общата изчислителна мощност на устройствата за копаене се е увеличила. Обратно, сигнал за намаляване на сложността ще бъде забавяне на търсенето на 2016 блока, тъй като хешрейтът на всички устройства е намалял. Резултатът е строг контрол върху скоростта, с която се емитират нови монети.

Къде да намерите трудност при копаене. Трудност при копаене на топ 10 на криптовалути.

Трудността при копаене е динамичен индикатор, който периодично се преизчислява. С нарастването на изчислителната мощност на оборудването за копаене нараства и сложността. Най-добре е да потърсите актуална информация за състоянието на трудността на копаене на криптовалута на официалните уебсайтове на валутите. Това обаче може да бъде трудно. Понякога е трудно да се намерят връзки към статистика за копаене дори на официални уебсайтове. За да се опрости процеса, бяха създадени уебсайтове агрегатори на статистическа информация за всички криптовалути. Те събират, обработват и публикуват текущи данни не само за трудността на добива, но и за няколко десетки други показатели: цена, капитализация, хешрейт, доходност, брой транзакции и т.н.

Актуална информация за повече от 100 криптовалути можете да намерите на следните уебсайтове:

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

* Моля, обърнете внимание, че трудността при копаене се променя с времето, така че различните сайтове може да предоставят различни данни за трудност. Понякога разликата достига 10-20% по валута на два различни агрегатора. Ако търсите индикатор за трудност при копаене не само за задоволяване на любопитството, но и за практически цели, тогава се съсредоточете върху средните числа. Например, ако правите прогноза за промените в трудността на копаене в бъдеще въз основа на историческа динамика, тогава е по-разумно да вземете данни за последните шест месеца до една година, а не за две до четири седмици.

** Някои криптовалути не могат да се копаят в традиционния смисъл. Някои използват POS майнинг, при който периодично се начислява лихва върху монетите в портфейла. За POS копаене не е необходимо да купувате специализирано оборудване и да харчите пари за електричество. Други криптовалути (например Ripple) вече са напълно добити и се преразпределят само между собствениците.

Трудност при копаене: какво засяга и защо расте.

Трудността на добива определя доходите на миньора. Броят на добитите монети е обратно пропорционален на трудността на копаене. Ако трудността на мрежата се увеличи с 20%, тогава доходът от криптовалута на всеки отделен майнер се намалява с 20%.

Например, ASIC за копаене на биткойн antminer s7 в средата на 2017 г. (по-точно, с трудности към 1 юли 2017 г.) копае 0,06 BTC на месец. Но сложността на биткойн мрежата непрекъснато нараства. От 1 ноември 2017 г. същото оборудване вече ще произвежда 0,026 BTC на месец. Приходите на миньора са паднали повече от половината само за 4 месеца.

Но дори седмичното намаление на доходите не прави инвестициите в копаене по-малко привлекателни. Приходите в криптовалута са частично компенсирани от увеличението на обменния курс към фиат. В нашия пример на 1 юли курсът на биткойн беше 2400 долара, а на 1 ноември котировките се повишиха до почти 6700 долара. Оказва се, че доходите на фиат миньорите са се увеличили дори въпреки бързото нарастване на сложността на копаене.

Това е логиката на създателите на криптовалути с динамична сложност. И въпреки че няма пряка връзка между цената на една валута и колко трудна е тя за копаене, все пак има косвена връзка. Предполага се, че увеличаването на сложността означава увеличаване на популярността на криптовалутата сред общото население. Някой, който научи за децентрализираните валути, ще се опита да копае. Това ще доведе до повишена сложност. Но в същото време е много вероятно търсенето да се увеличи, а следователно и обменният курс. Оказва се, че нарастващият интерес в обществото стимулира както растежа на валутния курс, така и увеличаването на сложността на копаене.

От техническа гледна точка индикаторът за трудност при копаене зависи от:

• хешрейт на мрежата (броят и изчислителната мощност на оборудването на всички миньори);
• скорост на копаене на 2016 блока;

И трите показателя са пряко свързани. Нарастването на хешрейта на мрежата означава, че нови участници са се присъединили към минната индустрия и конкуренцията се е увеличила. С увеличаването на броя на копачите времето, прекарано в търсене на следващия блок, намалява. След блок 2016 трудността при копаене се преизчислява. Промяната в индикатора се описва със следния модел:

Трудност при копаене на биткойни.

Увеличаването на сложността се дължи на редица фактори, които са тясно свързани помежду си:

• разработване на ASIC чипове и навлизане на пазара на по-производителни модели;
• популяризиране на Bitcoin и приток на нови копачи;
• висока възвръщаемост на инвестициите в копаене поради бързия растеж на обменния курс на биткойн спрямо долара;
• прехвърляне на изчислителна мощност от други валути, чиито котировки падат или растат по-бавно от биткойн;
• други фактори;

Трудността при копаене на биткойн се е увеличила 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++:

Всички изисквания за сложност в този раздел са посочени единствено по отношение на броя на операциите върху съдържащите се обекти.

когато се каже, че една операция има "постоянна сложност", това обикновено се отнася предимно до времевата сложност. Може да имам предвид пространствена сложност, но ако случаят е такъв, това ще бъде изрично посочено като нормално.

Сега, сложността на една операция се отнася до това колко време за завършване на операция ще се увеличи, когато броят на елементите, обработени в операцията, се увеличи. За операция с постоянна сложност функцията ще отнеме същото време, независимо дали се обработват нула или десет милиона елемента.

swap() е постоянна сложност, защото без значение колко елемента има във вектора, операцията ще отнеме същото време.

щракнете върху списъка. е постоянна сложност, защото въпреки че може да отнеме известно време за разпределяне на нов елемент, това време за разпределяне не се увеличава, тъй като списъкът съдържа 10 милиона елемента (поне не в алгоритмичен смисъл - разбира се, ако свободната памет стане по-голяма и по-изчерпана, разпределението може да отнеме повече време, но от алгоритмична гледна точка има безкрайно количество памет).

push_back() на вектор се нарича "амортизирана" константа, защото в нормалния случай, когато преразпределението не трябва да се извършва, времето, което ще отнеме операцията, не е свързано с това колко елемента вече има във вектора - същото количество от отнема време за добавяне на нов един елемент към вектор с дължина нула спрямо вектор с дължина 10 милиона. Въпреки това, ако векторът трябва да бъде преразпределен, ще е необходимо да има копие на съществуващите елементи и това не е постоянна операция - това е линейна операция. Но се предполага, че векторът е проектиран по такъв начин, че преразпределенията да се случват рядко, така че да могат да бъдат амортизирани за много операции 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. Въпреки това, малко хора се интересуват от точното време: зависи от процесора, типа на данните , език за програмиране и много други параметри. Важна е само асимптотичната сложност, т.е. сложността, когато размерът на входните данни клони към безкрайност.

Да кажем, че някакъв алгоритъм трябва да изпълни 4n 3 + 7n условни операции, за да обработи n елемента от входните данни. Тъй като n се увеличава, крайното работно време ще бъде значително по-засегнато от повишаването на n до куб, отколкото от умножаването му по 4 или добавянето на 7n. Тогава те казват, че времевата сложност на този алгоритъм е O(n 3), т.е. зависи кубично от размера на входните данни.

Използването на главно O (или така наречената O-нотация) идва от математиката, където се използва за сравняване на асимптотичното поведение на функциите. Формално O(f(n)) означава, че времето за работа на алгоритъма (или количеството заета памет) расте в зависимост от размера на входните данни не по-бързо от някаква константа, умножена по f(n).

Примери

O(n) - линейна сложност

Например, алгоритъмът за намиране на най-големия елемент в несортиран масив има тази сложност. Ще трябва да преминем през всички n елемента на масива, за да разберем кой е максималния.

O(log n) - логаритмична сложност

Най-простият пример е двоично търсене. Ако масивът е сортиран, можем да проверим дали съдържа определена стойност, като използваме метода на разполовяване. Нека проверим средния елемент, ако той е по-голям от този, който търсим, тогава ще изхвърлим втората половина на масива - определено я няма. Ако е по-малко, тогава обратното - ще изхвърлим първоначалната половина. И така ще продължим да разделяме наполовина и накрая ще проверим log n елемента.

O(n 2) - квадратична сложност

Например алгоритъмът за сортиране чрез вмъкване има тази сложност. В каноничната реализация се състои от два вложени цикъла: единият за преминаване през целия масив, а вторият за намиране на мястото за следващия елемент във вече сортираната част. По този начин броят на операциите ще зависи от размера на масива като n * n, т.е. n 2.

Има и други оценки на трудност, но всички те са базирани на същия принцип.

Също така се случва времето на работа на алгоритъма изобщо да не зависи от размера на входните данни. Тогава сложността се означава като O(1) . Например, за да определите стойността на третия елемент от масив, не е необходимо да помните елементите или да ги преглеждате много пъти. Винаги просто трябва да изчакате третия елемент във входния поток от данни и това ще бъде резултатът, който отнема същото време за изчисляване за произволно количество данни.

Същото важи и за оценките на паметта, когато това е важно. Алгоритмите обаче могат да използват значително повече памет, когато увеличават размера на входните данни, отколкото други, но въпреки това работят по-бързо. И обратно. Това помага да се изберат най-добрите начини за решаване на проблеми въз основа на текущите условия и изисквания.