здрасти Днешният урок ще бъде малко по-различен от останалите. Ще се различава по това, че е само косвено свързан с Java. Въпреки това тази тема е много важна за всеки програмист. Ще говорим за алгоритми . Какво е алгоритъм? С прости думи, това е няHowва последователност от действия, които трябва да бъдат изпълнени, за да се постигне желаният резултат . Често използваме алгоритми в ежедневието. Например, всяка сутрин имате конкретна задача: отидете на учorще or на работа и в същото време бъдете:
- Облечени
- Чисто
- Fed
- Събудете се с помощта на будилник.
- Вземете душ и се измийте.
- Направете закуска и малко кафе or чай.
- Яжте.
- Ако не сте изгладor дрехите си предишната вечер, изгладете ги.
- Облечи се.
- Напусни къщата.
- Купете or изтеглете изданието от 1961 г. на Третия нов международен речник на Webster.
- Намерете всяко име от нашия списък в този речник.
- На лист хартия напишете pageта от речника, на която се намира името.
- Използвайте листчетата, за да сортирате имената.
for
цикъл, който изпълнява тази задача
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
Каква е сложността на този алгоритъм? Линеен, т.е. O(n). Броят на действията, които програмата трябва да извърши, зависи от това колко числа са й предадени. Ако има 100 числа в масива, ще има 100 действия (операции за показване на низове на екрана). Ако в масива има 10 000 числа, трябва да се извършат 10 000 действия. Може ли нашият алгоритъм да бъде подобрен по няHowъв начин? Не. Независимо от всичко, ще трябва да направим N преминавания през масива и да изпълним N оператора, за да покажем низове на конзолата. Помислете за друг пример.
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
Имаме празен LinkedList
, в който вмъкваме няколко числа. Трябва да оценим алгоритмичната сложност на вмъкването на едно число в LinkedList
нашия пример и How то зависи от броя на елементите в списъка. Отговорът е O(1), т.е. постоянна сложност . Защо? Обърнете внимание, че вмъкваме всяко число в началото на списъка. Освен това ще си спомните, че когато вмъкнете число в LinkedList
, елементите не се местят никъде. Връзките (or препратките) се актуализират (ако сте забравor How работи LinkedList, вижте един от нашите стари уроци ). Ако първото число в нашия списък е x
и вмъкнем числото y в началото на списъка, тогава всичко, което трябва да направим, е следното:
x.previous = y;
y.previous = null;
y.next = x;
Когато актуализираме връзките, не ни интересува колко числа вече има вLinkedList
, независимо дали едно or един мorард. Сложността на алгоритъма е постоянна, т.е. O(1).
GO TO FULL VERSION