Loading...
MartinBG avatar MartinBG 4803 Точки

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
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.