Дякую. Одразу скажу, що я не програміст. Але як для звичайної людини підхід видається дивним. По перше складність сортування 5 та 10 чисел ( у 4,5 рази складніше або у 2 рази). Якщо 10 чисел були б десятковими дробами з трьома або чотирма знаками після коми, то сортування десяти чисел зайняло б не 27 секунд. Далі, нівелювання коефіцієнту 1/2. Це ціла половина, це дуже багато. Ви відчули б різницю, якщо Вам запропонували працювати 4 години замість 8 за ту саму зарплатню?
Дякую за запитання. Ви підняли справді цікаву тему. Оцінка складності алгоритмів базується на певних припущеннях і переслідує певні цілі. Наприклад, ми припускаємо, що обробка кожного числа бере однакову кількість часу. Маєте рацію: людині простіше порівняти 85 та 38, аніж 2,5385 та 2,5358. У комп'ютера це бере однаковий час. Крім того, людина має властивість втомлюватися - коли чисел стане 100, ця втома дасться взнаки дуже швидко. Тому ми робимо певні припущення, які більш-менш відповідають платформі, що виконуватиме алгоритм. І тоді ми можемо отримати певну оцінку складності алгоритму. Цю оцінку потім можна покращити, використовуючи кращі припущення - якщо захочеться. І ця оцінка переслідує певні цілі. У даному разі нам важливо зрозуміти, як складність зростає із розміром задачі. Порівняємо ми n1^2 із n2^2 чи 0,5*n1^2 із 0,5*n2^2, складність зростає в (n1/n2)^2 разів. Для цієї цілі коефіцієнт 1/2 виявляється неважливим. Хоча, якщо нам оцінка складності потрібна, щоб дізнатися конкретний час роботи, то ця 1/2 нам буде потрібна. Користуючись вашою аналогією із зарплатнею, поставте себе на місце не працівника, а підприємця. Він хоче створити компанію та має оцінити потрібні кошти. У нього є 10 тисяч євро, а оцінка каже, що потрібно мільйон. Очевидно, що цю компанію за свої гроші він не запустить - і навіть якщо оцінка неточна: потрібно пів мільйона чи два мільйони, це не міняє ситуацію принципово. Йому треба шукати інвестиції на масштабі мільйонів. Якщо в нього є такі джерела інвестицій, то один мільйон потрібен чи два, це питання уточненої оцінки. Спочатку треба зрозуміти масштаб. Так що, чим можна нехтувати, а чим не варто, - це визначається цілями.
Якщо бажаєте підтримати (to donate) донатами наш лекторій, щоб було більше заходів та відеоматеріалів:
www.patreon.com/scientificmeetings
гарна лекція. Нарешті стало зрозуміло з алгоритмами що до чого))
Чудова лекція
Дякую!
Дякую за перегляд!
Дякую. Одразу скажу, що я не програміст. Але як для звичайної людини підхід видається дивним. По перше складність сортування 5 та 10 чисел ( у 4,5 рази складніше або у 2 рази). Якщо 10 чисел були б десятковими дробами з трьома або чотирма знаками після коми, то сортування десяти чисел зайняло б не 27 секунд. Далі, нівелювання коефіцієнту 1/2. Це ціла половина, це дуже багато. Ви відчули б різницю, якщо Вам запропонували працювати 4 години замість 8 за ту саму зарплатню?
Дякую за запитання. Ви підняли справді цікаву тему. Оцінка складності алгоритмів базується на певних припущеннях і переслідує певні цілі.
Наприклад, ми припускаємо, що обробка кожного числа бере однакову кількість часу. Маєте рацію: людині простіше порівняти 85 та 38, аніж 2,5385 та 2,5358. У комп'ютера це бере однаковий час. Крім того, людина має властивість втомлюватися - коли чисел стане 100, ця втома дасться взнаки дуже швидко. Тому ми робимо певні припущення, які більш-менш відповідають платформі, що виконуватиме алгоритм. І тоді ми можемо отримати певну оцінку складності алгоритму. Цю оцінку потім можна покращити, використовуючи кращі припущення - якщо захочеться.
І ця оцінка переслідує певні цілі. У даному разі нам важливо зрозуміти, як складність зростає із розміром задачі. Порівняємо ми n1^2 із n2^2 чи 0,5*n1^2 із 0,5*n2^2, складність зростає в (n1/n2)^2 разів. Для цієї цілі коефіцієнт 1/2 виявляється неважливим. Хоча, якщо нам оцінка складності потрібна, щоб дізнатися конкретний час роботи, то ця 1/2 нам буде потрібна.
Користуючись вашою аналогією із зарплатнею, поставте себе на місце не працівника, а підприємця. Він хоче створити компанію та має оцінити потрібні кошти. У нього є 10 тисяч євро, а оцінка каже, що потрібно мільйон. Очевидно, що цю компанію за свої гроші він не запустить - і навіть якщо оцінка неточна: потрібно пів мільйона чи два мільйони, це не міняє ситуацію принципово. Йому треба шукати інвестиції на масштабі мільйонів. Якщо в нього є такі джерела інвестицій, то один мільйон потрібен чи два, це питання уточненої оцінки. Спочатку треба зрозуміти масштаб.
Так що, чим можна нехтувати, а чим не варто, - це визначається цілями.