801 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • ПРОХВЕСІЙНИЙ ПРОГРАМІСТ
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 13 386
    • Репутація: 5421

Re: Шлях на математичну вершину

Хтось оце може пояснити мені, як вони порахували найменшу необхідну кількість операцій для сортування масиву з унікальними числами?

Тут вони кажуть, що це буде n*log_2(n).
Кажуть - уявімо собі найгірший сценарій, коли всі числа в масиві є унікальними. Тоді у нас є n! пермутацій (це я вже на листочку перевірив), і лише в одній з пермутацій всі числа є відсортованими.
Алгоритм сортування повинен отримати достатньо інформації через процес порівняння, щоб ідентифікувати оту одну пермутацію.
Далі вони кажуть - якщо алгоритм закінчується після максимум f(n) кроків, то він не може відрізнити більше як 2^(f(n)) випадків, тому що числа різні, і кожне порівняння має лише два можливих результати.

Ось це я не розумію, звідки вони взяли те  2^(f(n)) ?

Подякували: mamkin haker1

802 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • ПРОХВЕСІЙНИЙ ПРОГРАМІСТ
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 13 386
    • Репутація: 5421

Re: Шлях на математичну вершину

mamkin haker написав:

Якщо алгоритм завжди завершується після більшості кроків f(n), він не може розрізняти більше 2^f(n) випадків,  оскільки ключі різні, і кожне порівняння має лише два можливих результату.

комбінаторика?
2 можливих результати означає шо вони можуть бути або на своїх місцях або ні,
тобто вони можуть як помінятись, так і ні ( то я так думаю )

я не шарю в комбінаториці, бо не вчився.

я ще й якось криво переклав.
Там не більшості кроків, а - завершується щонайбільше після f(n) кроків
два можливих результати, це або число А більше числа Б, або ні. True, або False.

Подякували: mamkin haker1

803 Відповідь від lucas-kane

  • lucas-kane
  • Користувач
  • Поза форумом
  • Дата реєстрації: 13.01.2021
  • Повідомлень: 215
    • Репутація: 126

Re: Шлях на математичну вершину

Для того, щоб переставити елементи місцями, їх потрібно порівняти. Ось це порівняння може давати 2 випадки (a>b) або (a<b). А f(n) - кількість кроків до завершення алгоритму... Ось тобі і 2^f(n) >= n!

Подякували: koala, tchort2

804 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • ПРОХВЕСІЙНИЙ ПРОГРАМІСТ
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 13 386
    • Репутація: 5421

Re: Шлях на математичну вершину

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 - це дофіга, але дофіга чого саме?

805 Відповідь від frz

  • frz
  • frz
  • Data / DB Engineer
  • Поза форумом
  • Звідки: PL
  • Дата реєстрації: 28.12.2019
  • Повідомлень: 5 085

Re: Шлях на математичну вершину

zearn.org - безкоштовний інтерактивний курс з математики від дитячого садка до ~8 класу.
Щоб було безкоштовно, потрібно ведучому класу вказати що він/вона - parent.

frz вебсайт

806 Відповідь від lucas-kane

  • lucas-kane
  • Користувач
  • Поза форумом
  • Дата реєстрації: 13.01.2021
  • Повідомлень: 215
    • Репутація: 126

Re: Шлях на математичну вершину

FakiNyan написав:
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 (Дональд Кнут), оцінка складності алгоритмів, аналіз алгоритмів

807 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 14 738
    • Репутація: 12514

Re: Шлях на математичну вершину

FakiNyan написав:
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^(довжина послідовності). Ось про це мова.

Подякували: mamkin haker, FakiNyan2

koala вебсайт

808 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • ПРОХВЕСІЙНИЙ ПРОГРАМІСТ
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 13 386
    • Репутація: 5421

Re: Шлях на математичну вершину

оцей чувак детально пояснив, там навіть інтеграли використовуються (щоб знайти  n log n)
https://www.youtube.com/watch?v=WffUZk1pgXE

Подякували: mamkin haker, leofun012