Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Швидкість алгоритмів та кількість елементів для обробки
Для відправлення відповіді ви повинні увійти або зареєструватися
Щось не то 10^1=10, 10^0=1
Вивести обернені функції для "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!?
І взагалі, а що саме розумієте під факторіалом нецілого числа? Гамма-функцію?
доречі lg то не log2, а log10
У різних книжках бува різне, навіть після стандартизації цього діла. І lg, і ld зустрічав на log2.
А загалом тут це не сильно важливо, однак оцінки з точністю до константного множника, ну хай не в мікросекундах, а в 0.301 мікросекунди тік буде ;-)
сподіваюсь, що ця дівка помиляється, бо тоді та таблиця не має жодного сенсу
Сенс таблички — показати, що слід з усіх сил у верхніх рядках залишатися 
, бо чим нижче, тим довше виписувати навіть число, яке відповідає часові роботи (а то виписування забирає lg n, між іншим, якщо писати у звичайній формі).
p.s. до речі, вправа — скільки (асимптотично) часу займає запис числа у формі a⋅10b при фіксованій точності мантиси a.
Які саме вирази використовувалися для 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.
І взагалі, а що саме розумієте під факторіалом нецілого числа? Гамма-функцію?
Так, n! = Gamma(n+1).
upd: Якщо цікавить виведення оберненої функції для Стірлінга, то можна глянути на stackexchange.
запис числа у формі 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))
Для відправлення відповіді ви повинні увійти або зареєструватися
