4. Truck Tour - Exercises: Objects, Classes and Collections - Решение с линейна сложност

Прегледах записа от упражнението, както и няколко решения на колеги от предишни издания на курса в GitHub, и забелязах, че всички подхождат по аналогичен начин към проблема и използват алгоритъм с квадратична сложност за решаване на задачата.

Това е решението от упражнението:

Може да е заради желанието непременно да се използва опашка, но все пак реших да споделя и едно решение с масив, което е с линейна сложност.

Разликите в бързодействието са огромни и над определен брой елементи наивното (квадратично) решение практически спира да работи.

20000 + 2 елемента:

Number of elements (fuel pumps): 20002

Linear Algorithm (array)...
Elapsed time in milliseconds: 6
Counter: 60003
Start index: 20001

Quadratic Algorithm (queue)...
Elapsed time in milliseconds: 1881
Counter: 200050003
Start index: 20001

50000 + 2 елемента:

Number of elements (fuel pumps): 50002

Linear Algorithm (array)...
Elapsed time in milliseconds: 12
Counter: 150003
Start index: 50001

Quadratic Algorithm (queue)...
Elapsed time in milliseconds: 15763
Counter: 1250125003
Start index: 50001

Надявам се този пост да събуди интереса на повече колеги към алгоритмите и намирането на ефективни решения, а също и да вдигне малко нивото на курса...

По принцип си прав, но в задачите от определна лекция се очаква да се използва изучавания материал от лекцията. Схемата на Наков за обучение е да се учат нещата едно по едно. По-нататък в курса казаха, че ще оценяват по качество на кода, но на този етап са базови неща. Но съм напълно съгласен, че трябва да се вдигне нивото, защото нещата вървят много мудно, а има много какво да се учи. Щеше ми се да беше включен курса за алгоритми, вместо да е веднъж годишно.

Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.

4. Truck Tour - Exercises: Objects, Classes and Collections - Решение с линейна сложност