21

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

Щось не то 10^1=10, 10^0=1

22 Востаннє редагувалося yooll (08.12.2017 07:57:35)

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

leofun01 написав:

Вивести обернені функції для "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"
    }
}

Які саме вирази використовувалися для nlgn та n!?
І взагалі, а що саме розумієте під факторіалом нецілого числа? Гамма-функцію?

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

23

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

Vo_Vik написав:

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

У різних книжках бува різне, навіть після стандартизації цього діла. І lg, і ld зустрічав на log2.

А загалом тут це не сильно важливо, однак оцінки з точністю до константного множника, ну хай не в мікросекундах, а в 0.301 мікросекунди тік буде ;-)

24 Востаннє редагувалося ReAl (08.12.2017 16:08:49)

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

FakiNyan написав:

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

Сенс таблички — показати, що слід з усіх сил у верхніх рядках залишатися :D, бо чим нижче, тим довше виписувати навіть число, яке відповідає часові роботи (а то виписування забирає lg n, між іншим, якщо писати у звичайній формі).

p.s. до речі, вправа — скільки (асимптотично) часу займає запис числа у формі a⋅10b при фіксованій точності мантиси a.

25 Востаннє редагувалося leofun01 (10.12.2017 02:18:53)

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

yooll написав:

Які саме вирази використовувалися для nlgn та n!?

Для x(n) = n*log2(n) обернена функція :
n(x) = ln(2)*x/W(ln(x)*x),
де W(x) - функція Ламберта, загалом вона багатозначна, але я використовував тільки основну гілку. Її можна наближено обчислити використовуючи ряди з коефіцієнтами, де чисельники A227831, а знаменники A095996.

Значення функції x(n) = n! при великих n досить добре наближує формула Стірлінга.
Для апроксимації обернена функція :
n(x) = ln(x/sqrt(2*pi))/W(exp(-1)*ln(x/sqrt(2*pi)))-1/2.

yooll написав:

І взагалі, а що саме розумієте під факторіалом нецілого числа? Гамма-функцію?

Так, n! = Gamma(n+1).

upd: Якщо цікавить виведення оберненої функції для Стірлінга, то можна глянути на stackexchange.

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

26 Востаннє редагувалося leofun01 (10.12.2017 03:06:07)

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

ReAl написав:

запис числа у формі a⋅10b при фіксованій точності мантиси a.

До речі, в першому рядку таблиці потрібно було записати значення функції оберненої до log2(n), тобто 2^x, де x я брав з третього рядка таблиці. І компютер відмовлявся обчислювати 2^(c*10^p) навіть наближено.
Тоді виникло питання, як число 2^(c*10^p) представити у вигляді a*10^b, де b - ціле, a - дійсне між 1 і 10 (10 не включається).
a*10^b = 2^(c*10^p),
log2(a*10^b) = c*10^p,
log2(a) + log2(10^b) = c*10^p,
ln(a)/ln(2) + ln(10^b)/ln(2) = c*10^p,
ln(a) + ln(10^b) = ln(2)*c*10^p,
ln(a) + b*ln(10) = ln(2)*c*10^p,
b*ln(10) = ln(2)*c*10^p - ln(a),
b = ln(2)/ln(10)*c*10^p - ln(a)/ln(10),
b = log10(2)*c*10^p - log10(a),
c і p - відомі, a - не відоме, але ми знаємо, що a < 10, тобто log10(a) < 1, тому можемо записати що
b = floor(log10(2)*c*10^p),

b = floor(ln(2)/ln(10)*c*10^p)

, де floor(x) повертає найбільше ціле число менше за (або рівне) x.
Тепер b - відоме і можна знайти a :
log2(a) = c*10^p - log2(10^b),
log2(a) = c*10^p - b*log2(10),
a = 2^(c*10^p - b*log2(10)),

a = 2^(c*10^p - b*ln(10)/ln(2))
Подякували: 221VOLT, koala2

27

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

Виведення можна різко скоротити, якщо одразу логарифмувати по 10. І цілу частину в математиці зазвичай позначають [x], ну і c*10^p не обов'язково всюди повторювати :)
e = c*10^p    //# exponent, показник
b = [e*lg10(2)]
a = 2^(e-b/lg10(2))

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

28

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

Прихований текст

про щоооооо вони балакають...... краще б з доведенням допомогли...

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