Содержание
- 2. Вступ Сьогодні ми поговоримо про: спостереження математичні моделі класифікацію за порядком зростання теорію алгоритмів пам’ять
- 3. Чарльз Беббідж «Як тільки Аналітична Машина буде створена, вона буде спрямовувати майбутній розвиток науки. Кожний раз
- 4. Running time За Беббіджем, час роботи вашого алгоритму вимірювався в тому, скільки разів ви маєте прокрутити
- 5. Причини аналізувати алгоритми Ми аналізуємо алгоритми що б: Оцінити продуктивність Порівняти алгоритми Надати гарантії обчислюваності/виконуваності Зрозуміти
- 6. Дискретне перетворення Фур'є Дискретне перетворення Фур'є (ДПФ, Discrete Fourier Transform) - це математична процедура, що використовується
- 7. Проблема Основне питання, що ставить собі програміст – чи зможе моя програма вирішити поставлену задачу на
- 8. Науковий підхід, що застосовується для аналізу алгоритмів Науковий підхід: спостереження, якихось характеристик з реального світу, зазвичай
- 9. Принципи наукового підходу Експерименти мають бути відтворюємими, що б інші могли впевнитися в вірності моделі, самостійно
- 10. Спостереження Почнемо з спостереження. 3-Sum. Дано N різних цілих чисел, скільки трійок в сумі дають 0?
- 11. Вимірювання часу роботи Як виміряти час роботи програми? Вручну. http://standart-m.com.ua/userfiles/image/stopwatch1.jpg
- 12. Вимірювання часу роботи Як виміряти час роботи програми? Автоматично. Ми можемо скористатися класом Stopwatch() int[] a
- 13. Емпіричний аналіз Ми можемо запустити програму на різних об’ємах даних і оцінити витрачений час. Давайте спробуємо
- 14. Емпіричний аналіз
- 15. Аналіз даних Зобразимо графічно залежність T(N) від N
- 16. Аналіз даних
- 17. Аналіз даних Тепер ми отримали гіпотезу на основі гіпотези ми можемо спрогнозувати дані після чого провести
- 18. Аналіз даних Незалежні чинники Алгоритм Вхідні дані визначають значення b в степені. Чинники залежні від системи
- 19. Математична модель Д. Кнут – «незважаючи на складність, в принципі можливо побудувати математичну модель, що описує
- 20. Математична модель Вартість базових операцій
- 21. Математична модель Вартість базових операцій
- 22. Математична модель Скільки інструкцій буде виконано в залежності від N? int count = 0; for (int
- 23. Математична модель Скільки інструкцій буде виконано в залежності від N? int count = 0; for (int
- 24. Математична модель «Дуже зручно мати міру об’єму робіт, навіть якщо вона буде дуже сира. Ми можемо
- 25. Математична модель Замість того, що б обраховувати прискіпливо всі операції ми можемо ігнорувати відносно малі операції
- 26. Математична модель Приклади апроксимації
- 27. Математична модель
- 28. Математична модель
- 29. Математична модель
- 30. Математична модель В принципі, математична модель можлива. На практиці: формули можуть бути дуже складними дуже складні
- 31. Класифікація за порядком зростання
- 32. Класифікація за порядком зростання
- 33. Класифікація за порядком зростання
- 34. Бінарний пошук Дано відсортований масив і ключ, потрібно знайти індекс ключа в масиві. Бінарний пошук: порівнюємо
- 35. Бінарний пошук Перший алгоритм бінарного пошуку опублікований в 1964 році Перший алгоритм без помилок – в
- 36. Бінарний пошук: математичний аналіз
- 37. N2logN алгоритм для 3-суми Алгоритм базований на сортуванні для 3-суми Відсортувати N чисел Для кожної пари
- 38. Порівняння brute-force sorting-based
- 39. Аналіз В реальності наші приклади набагато складніші ніж ті, що ми розглядали. І складність нашого алгоритму
- 40. Аналіз
- 41. Теорія алгоритмів Основними цілями теорії алгоритмів є: визначити «складність» проблеми запропонувати «оптимальний» алгоритм Оптимальний алгоритм: Має
- 42. Загально прийняті позначення в теорії алгоритмів
- 43. Теорія алгоритмів. Приклад 1.
- 44. Теорія алгоритмів. Приклад 2.
- 45. Пам’ять
- 46. Типові показники використання пам’яті
- 47. Типові показники використання пам’яті об’єктами в Java Заголовок об’єкта. 16 байт Вказівник. 8 байт Доповнення. Кожний
- 48. Приклад 2
- 49. Приклад.
- 50. Приклад.
- 52. Скачать презентацию