search

kzhereb / kpi-acts-ta2020

Materials for "Algorithm theory" course
MIT License
0 stars 0 forks source link

Q02.12 Порівняти теоретичні складності big-O з практичними вимірами #8

Open K4TEL opened 4 years ago

K4TEL commented 4 years ago

Ресурси де порівнюють теоретичні оцінки складності алгоритмів з конкретними вимірами. Бажано що були деталі вимірів. Додаткові бали за порівняння вимірів коду з benchmark'ів на своєму пристрої з опублікованими.

Resources where theoretical estimates of the complexity of algorithms are compared with specific measurements. It is desirable that there were details of measurements. Additional points for comparing code measurements from benchmarks on your device with published ones.

K4TEL commented 4 years ago

https://www.bigocheatsheet.com/ сайт з теоретичними вимірами для найвідоміших алгоритмів сортування та структур даних. Є можливість переходу на окремі сторінки для подальшого вивчення.

K4TEL commented 4 years ago

O(n2): known as Quadratic complexity

1 item: 1 second 10 items: 100 seconds 100 items: 10000 seconds

O(n): known as Linear complexity

1 item: 1 second 10 items: 10 seconds 100 items: 100 seconds

O(1): known as Constant complexity

1 item: 1 second 10 items: 1 second 100 items: 1 second

O(log n): known as Logarithmic complexity

1 item: 1 second 10 items: 2 seconds 100 items: 3 seconds 1000 items: 4 seconds 10000 items: 5 seconds

Виміри часу, що відповідають кожній складності big-O.

K4TEL commented 4 years ago

https://sagarpatel8384.github.io/big-o/benchmarking/2016/03/01/big-o-notation-and-benchmarking/ корисна стаття про benchmark'и. Особливо корисна буде для тих. хто використовує Ruby, оскільки наведено API для застосування.

K4TEL commented 4 years ago

Singly Linked List Time for append operation, 3000 times: 0.06164 Time for find operation, 3000 times: 2.31469 Time for get operation, 3000 times: 1.88473 Time for get_reversed operation, 1 time: 0.01833 Time for pop operation, 3000 times: 1.96568 Time for clear operation, 1 time: 0.0006

HashMap Time for put operation, 30000 times: 0.85135 Time for get operation, 30000 times: 0.13367 Time for remove operation, 23630 times: 0.47738 Time for getKeys operation, 100 times: 4.00562 Time for getValues operation, 100 times: 3.98825

PickDough commented 4 years ago

https://www.measurethat.net/Benchmarks/Show/1475/0/versions-of-quick-sort Ось чудовий ресурс, де можна порівнювати будь-які реалізації алгоритмів, а також навіть веб застосунки. Час у даному прикладі вказано у операція/секунда і одразу відображено швидшу з реалізацій(після запуску).