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)
А де число?

All you want is a dingle,
What you envy's a schwang,
A thing through which you can tinkle,
Or play with, or simply let hang...

2

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

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

3

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

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

All you want is a dingle,
What you envy's a schwang,
A thing through which you can tinkle,
Or play with, or simply let hang...
Подякували: 0xDADA11C71

4

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

ви робите не те, не так і не туди
Ви не те робите, для веб макакінга потрібно не лише вчити, а й забувати! Не будьте білим крукоммакакієм, бо так вам ніколи на роботу не влаштуватися.
Говорила баба діду: «Я поїду к Білодіду, Ізучу двомовну мову І вернусь обратно знову». А дід бабі: «Не *изди, К Білодіду нєт їзди, — Туди не ходять поїзди»
Подякували: 221VOLT, leofun012

5

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

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

All you want is a dingle,
What you envy's a schwang,
A thing through which you can tinkle,
Or play with, or simply let hang...

6 Востаннє редагувалося 221VOLT (07.12.2017 18: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.

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

Це ще не кінець. Це навіть не початок кінця. Але, можливо, це кінець початку.
Зростання мудрості можна точно вимірювати ступенем зменшення злоби.

https://coderhero.win/ Розбудовуємо інтернет разом!

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

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

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

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

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

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

All you want is a dingle,
What you envy's a schwang,
A thing through which you can tinkle,
Or play with, or simply let hang...

8

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

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

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

All you want is a dingle,
What you envy's a schwang,
A thing through which you can tinkle,
Or play with, or simply let hang...

9

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

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

Це ще не кінець. Це навіть не початок кінця. Але, можливо, це кінець початку.
Зростання мудрості можна точно вимірювати ступенем зменшення злоби.

https://coderhero.win/ Розбудовуємо інтернет разом!

10 Востаннє редагувалося dot (07.12.2017 19: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

All you want is a dingle,
What you envy's a schwang,
A thing through which you can tinkle,
Or play with, or simply let hang...
Подякували: 221VOLT1

12

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

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

13

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

Vo_Vik написав:

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

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

All you want is a dingle,
What you envy's a schwang,
A thing through which you can tinkle,
Or play with, or simply let hang...

14

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

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

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

15

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

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

16

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

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

17 Востаннє редагувалося koala (07.12.2017 20: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

All you want is a dingle,
What you envy's a schwang,
A thing through which you can tinkle,
Or play with, or simply let hang...
Подякували: 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