Софтуерно Инженерство
Loading...
+ Нов въпрос
MartinBG avatar MartinBG 1169 Точки

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

Условие

Judge

Прегледах записа от упражнението, както и няколко решения на колеги от предишни издания на курса в 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

 

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

 

0
Java Advanced 06/10/2017 05:48:54
stoiko.bogev avatar stoiko.bogev 78 Точки

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

0