1

Тема: Швидкість алгоритмів та кількість елементів для обробки

Читаю книженцію, і тут пишуть
https://cdn.discordapp.com/attachments/333936584481177600/388338450668978200/unknown.png
що я перекладаю як

Для кожної хвункції f(n) та часу t в наступній таблиці, визначте найбільше число елементів n для проблеми, котра може бути вирішена за час t, припускаючи, що алгоритм вирішує проблему в f(n)
мікросекунд

І дається така ось табличка https://cdn.discordapp.com/attachments/333936584481177600/388340502313041960/unknown.png

Так я не можу зрозуміти, як то вірно рахувати, але пробую ось так.

Якщо f(n) повертає мікросекунди, а це 1/106 секунди, то рівняння для однієї секунди має бути записано тако
106 = log2(n)
ну от я записую то в wolfram alpha, а воно мені якусь фігню повертає
https://www.wolframalpha.com/input/?i=10%5E6%3Dlog_2(x)
А де число?

2

Re: Швидкість алгоритмів та кількість елементів для обробки

У вас проблема з алгоритмами чи з мовою Wolfram Alpha? У чому саме ваше питання?

3

Re: Швидкість алгоритмів та кількість елементів для обробки

От я і не знаю, в чому саме проблема. Ви скажіть мені.

Подякували: 0xDADA11C71

4

Re: Швидкість алгоритмів та кількість елементів для обробки

ви робите не те, не так і не туди

Ви не те робите, для веб макакінга потрібно не лише вчити, а й забувати! Не будьте білим крукоммакакієм, бо так вам ніколи на роботу не влаштуватися.

Подякували: 221VOLT, leofun012

5

Re: Швидкість алгоритмів та кількість елементів для обробки

я нічого не пойняв з того, що ви сказали, краще поясніть мені, чи я правильну хвормулу написав, і якщо так - то чого WA не дав мені розв'язку?? мені треба заповнити табличку!

6 Востаннє редагувалося 221VOLT (07.12.2017 17:49:24)

Re: Швидкість алгоритмів та кількість елементів для обробки

FakiNyan написав:

От я і не знаю, в чому саме проблема. Ви скажіть мені.

це щось типу як у ситуації з vanitygen - генеруванням брутфорсом біткоін-адреси з певними символами спочатку
(типу красота)

перші декілька символів знайдуться швидко, 5+ -- довго і дуже довго
https://en.bitcoin.it/wiki/Vanitygen#Di … g_a_vanity
https://bits.media/bitcoin-address-practice/#9

vanity     difficulty     average time
1B     22     < 1s
1Bi     1,330     < 1s
1Bit     77,178     < 1s
1Bitc     4,476,342 (4.48E+6)     < 10s
1Bitco     259,627,881 (2.6E+8)     3 minutes
1Bitcoi     15,058,417,127 (1.506E+10)     3 hours
1Bitcoin     8.7339E+11     1 week
1BitcoinE     5.0657E+13     1 year
1BitcoinEa     2.9381E+15     60 years
1BitcoinEat     1.7041E+17     3,500 years
1BitcoinEate     9.8837E+18     200,000 years
1BitcoinEater     5.7325E+20     11,700,000 years
1BitcoinEaterAddressDontSend     1.6209E+47     3.3E+33 or 3.3 decillion years.

тільки тут одна функція, у вас - різні
і потрібно знайти значення

7 Востаннє редагувалося FakiNyan (07.12.2017 17:54:20)

Re: Швидкість алгоритмів та кількість елементів для обробки

я зрозумів завдання, не тре його повторювати....

Здається, я зрозумів проблему WA. Вже при t=100 воно повертає
1267650600228229401496703205376

Ну а при мільйоні там якийсь гугол вийде, це ж по суті
2 в степені 1000000

Але як вони тоді хочуть, аби я записав ті числа в таблицю? Майбуть, я таки роблю щось не так.

8

Re: Швидкість алгоритмів та кількість елементів для обробки

хто б міг подумати, що дівка з московії, котра балакає англійською і сидить на математичному сервері в діскорді дасть відповідь першою... виходе, що я все роблю правильно, і такі здорові числа треба записувати як
10301030

сподіваюсь, що ця дівка помиляється, бо тоді та таблиця не має жодного сенсу

9

Re: Швидкість алгоритмів та кількість елементів для обробки

1.2e33 чи скільки там

10 Востаннє редагувалося dot (07.12.2017 18:10:13)

Re: Швидкість алгоритмів та кількість елементів для обробки

Гадаю, що

  • lg n то log10 n

  • Тре знайти n за ту мікросекунду, а далі просто множеш на час; чим більше число, тим краще

WA не показує, тому що наднадто надздорове число.

Подякували: 221VOLT1

11

Re: Швидкість алгоритмів та кількість елементів для обробки

так це 1 секунда, а уявіть собі, як виглядатиме число за 1 століття...
це ж
1000000*60*60*24*365
Мабуть, ось така картинка краще показує різницю між формулками
https://cdn.discordapp.com/attachments/333936584481177600/388360815507537924/unknown.png

Подякували: 221VOLT1

12

Re: Швидкість алгоритмів та кількість елементів для обробки

Наскільки я зрозумів з англійської версії, то час роботи алгоритму в мікросекундах дорівнє значенню яке повертає фунція.
відповідно треба знайти найбільше значення параметру при якому значення фунції менше за t.
Найсладніше що там є то певно n * lg n  і n!

13

Re: Швидкість алгоритмів та кількість елементів для обробки

Vo_Vik написав:

Наскільки я зрозумів з англійської версії, то час роботи алгоритму в мікросекундах дорівнє значенню яке повертає фунція.
відповідно треба знайти найбільше значення параметру при якому значення фунції менше за t.
Найсладніше що там є то певно n * lg n  і n!

повідомлення не читай - відразу відповідай

14

Re: Швидкість алгоритмів та кількість елементів для обробки

То просто думки в голос.

Подякували: FakiNyan1

15

Re: Швидкість алгоритмів та кількість елементів для обробки

доречі lg то не log2, а log10

16

Re: Швидкість алгоритмів та кількість елементів для обробки

Чисто програмно, ця задачка зводиться до пошуків розвязку рівння з точністю до 1

17 Востаннє редагувалося koala (07.12.2017 19:41:39)

Re: Швидкість алгоритмів та кількість елементів для обробки

Все ж краще писати 210^6 - бо в останньому стовпчику там буде трохи більше знаків в найвищому ступені :)
І, зрештою, існують задачі, для яких придумували спеціальні нотації. 3↥↥3 в нотації Кнута значно більше, ніж добуток усіх чисел у цій таблиці.

Подякували: FakiNyan, 221VOLT, leofun013

18

Re: Швидкість алгоритмів та кількість елементів для обробки

Vo_Vik написав:

доречі lg то не log2, а log10

раніше в цій книзі теж використовувалось lg, і вони сказали, що в них це log2
https://cdn.discordapp.com/attachments/333936584481177600/388382172702179338/unknown.png

Подякували: 221VOLT1

19

Re: Швидкість алгоритмів та кількість елементів для обробки

FakiNyan написав:
Vo_Vik написав:

доречі lg то не log2, а log10

раніше в цій книзі теж використовувалось lg, і вони сказали, що в них це log2
https://cdn.discordapp.com/attachments/333936584481177600/388382172702179338/unknown.png

Цікаві вони люди.

Подякували: 221VOLT1

20

Re: Швидкість алгоритмів та кількість елементів для обробки

Вивести обернені функції для "n!" і "n*log2(n)" було дуже не просто.
Вийшло якось так :

{
    "log2(n)": {
        "sec" : "9.90065 * 10^301029",
        "min" : "5.49337 * 10^18061799",
        "hour": "2.45658 * 10^1083707984",
        "day" : "2.33332 * 10^26008991625",
        "mont": "1.09460 * 10^780269748761",
        "year": "4.49744 * 10^9499784191165",
        "cent": "1.97973 * 10^949978419116565"
    },
    "sqrt(n)": {
        "sec" : "1.00000 * 10^12",
        "min" : "3.60000 * 10^15",
        "hour": "1.29600 * 10^19",
        "day" : "7.46496 * 10^21",
        "mont": "6.71846 * 10^24",
        "year": "9.95882 * 10^26",
        "cent": "9.95882 * 10^30"
    },
    "n": {
        "sec" : "1.00000 * 10^6",
        "min" : "6.00000 * 10^7",
        "hour": "3.60000 * 10^9",
        "day" : "8.64000 * 10^10",
        "mont": "2.59200 * 10^12",
        "year": "3.15576 * 10^13",
        "cent": "3.15576 * 10^15"
    },
    "n*log2(n)": {
        "sec" : "6.27461 * 10^4",
        "min" : "2.80141 * 10^6",
        "hour": "1.33378 * 10^8",
        "day" : "2.75514 * 10^9",
        "mont": "7.18708 * 10^10",
        "year": "7.98160 * 10^11",
        "cent": "6.86565 * 10^13"
    },
    "n^2": {
        "sec" : "1.00000 * 10^3",
        "min" : "7.74596 * 10^3",
        "hour": "6.00000 * 10^4",
        "day" : "2.93938 * 10^5",
        "mont": "1.60996 * 10^6",
        "year": "5.61761 * 10^6",
        "cent": "5.61761 * 10^7"
    },
    "n^3": {
        "sec" : "1.00000 * 10^2",
        "min" : "3.91486 * 10^2",
        "hour": "1.53261 * 10^3",
        "day" : "4.42083 * 10^3",
        "mont": "1.37365 * 10^4",
        "year": "3.16010 * 10^4",
        "cent": "1.46679 * 10^5"
    },
    "2^n": {
        "sec" : "1.99315 * 10^1",
        "min" : "2.58384 * 10^1",
        "hour": "3.17453 * 10^1",
        "day" : "3.63303 * 10^1",
        "mont": "4.12372 * 10^1",
        "year": "4.48430 * 10^1",
        "cent": "5.14869 * 10^1"
    },
    "n!": {
        "sec" : "9.44560 * 10^0",
        "min" : "1.11663 * 10^1",
        "hour": "1.27888 * 10^1",
        "day" : "1.39966 * 10^1",
        "mont": "1.52488 * 10^1",
        "year": "1.61463 * 10^1",
        "cent": "1.77570 * 10^1"
    }
}
Подякували: yooll, koala, FakiNyan, 221VOLT4