Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Шлях на математичну вершину
zearn.org - безкоштовний інтерактивний курс з математики від дитячого садка до ~8 класу.
Щоб було безкоштовно, потрібно ведучому класу вказати що він/вона - parent.
lucas-kane написав:Для того, щоб переставити елементи місцями, їх потрібно порівняти. Ось це порівняння може давати 2 випадки (a>b) або (a<b). А f(n) - кількість кроків до завершення алгоритму... Ось тобі і 2^f(n) >= n!
Ви практично 1 в 1 сказали те саме, що й я написав зверху, але без пояснення, чому воно так, котре я й намагаюсь віднайти.
Що оте 2^f(n) взагалі таке? От нехай у нас є бульбашкове сортування, маємо 5 елементів, і 25 кроків, бо O(n^2). Якщо це 5 відмінних елементів, то загальна кількість пермутацій 120, бо 5!. 2^25 - це дофіга, але дофіга чого саме?
Так точно вирахувати, як ти хочеш так не вийде (це так не працює). Шукай за темами BIG O (Дональд Кнут), оцінка складності алгоритмів, аналіз алгоритмів
lucas-kane написав:Для того, щоб переставити елементи місцями, їх потрібно порівняти. Ось це порівняння може давати 2 випадки (a>b) або (a<b). А f(n) - кількість кроків до завершення алгоритму... Ось тобі і 2^f(n) >= n!
Ви практично 1 в 1 сказали те саме, що й я написав зверху, але без пояснення, чому воно так, котре я й намагаюсь віднайти.
Що оте 2^f(n) взагалі таке? От нехай у нас є бульбашкове сортування, маємо 5 елементів, і 25 кроків, бо O(n^2). Якщо це 5 відмінних елементів, то загальна кількість пермутацій 120, бо 5!. 2^25 - це дофіга, але дофіга чого саме?
Можливих результатів порівнянь. Насправді, як ви правильно зауважили, їх менше, але це тільки тому, що там є зайві.
Спробую так це описати. Є алгоритм сортування, який використовує функцію для порівняння. Нехай функція не просто повертає bool (менше чи ні), а записує цей bool - що в файл, що на екран. І там виникає послідовність True/False чи 1/0. Кожна послідовність однозначно описує процес сортування. Скільки таких послідовностей може бути в принципі? 2^(довжина послідовності). Ось про це мова.
оцей чувак детально пояснив, там навіть інтеграли використовуються (щоб знайти n log n)
https://www.youtube.com/watch?v=WffUZk1pgXE
Хтось оце може пояснити мені, як вони порахували найменшу необхідну кількість операцій для сортування масиву з унікальними числами?
Тут вони кажуть, що це буде n*log_2(n).
..
Знайшли відповідь? поділіться з іншими, може комусь згодиться.
звідки вони взяли те 2^(f(n))
Не знаю їх ланцюжок роздумів і як її використовують, але сама функція не важка. Це відображення n -> m, де кількість можливих результатів - n^m, 2^(f(n)).
Якщо на пальцях : у вас є два унікальних значення (ліво - право, або (0,1)). Необхідно знайти скільки можливих комбінацій (0,1) довжино 2 : (0,0),(0,1),(1,0),(1,1). тобто 2^2=4, якщо довжина 3 то 2^3=8, (0,0,0),(0,0,1)..ітд.
До цієї кількості операцій можна спробувати дійти самому якщо спробувати реалізувати один з алгоритмів сортування(merge, quick..).
Якщо сортувати бульбашкою масив розміром n, то там один цикл n в іншому циклі n (є деяка оптимізація в кінці, але то таке..) тому його швидкість(швидше повільність) буде О(n^2).
Уявімо що ви хочете відсортувати масив в два рази більше, значить швидкість буде О((2n)^2)=О(4n^2), а чи не простіше 2 рази відсортувати зліва і зправа, щоб операцій було хоч не в 2 рази більше але точно не в 4?! Є такі алгоритми, і в ідеальному випадку вони працюють наче на повному бінарному дереві (завжди відбувається розбиття і в ідеальному випадку на середині (вибір pivot у quick)).
А як ми знаємо, якщо в повному бінарному дереві n елементів, то глибина дерева буде log_2(n).
Ось звідки взялось n*log_2(n).
Квадрат можна нарізати так щоб з отриманих частин зібрати круг, і наоборот. Я не знав що таке взагалі можливо.
Розібрав тему трохи детальніше, і все таки там є фрактальні елементи, це значить що ножицями вирізати з паперу їх не вийде. І ця анімація є тільки наближеням одного з знайдених розкладів.
І знайшов видиво, де детально пояснено як вдалось побудувати такий роклад :
Послідовність Морзе-Туе 01101001.. - не очікував побачити там дзета-функцію.. гарний результат.
