TechCodeview

Алгоритъмът е поредица от инструкции, които се изпълняват в предварително определена последователност, за да се реши проблем или да се завърши работа. Функцията е блок от код, който може да бъде извикан и изпълнен от други части на програмата.

Набор от инструкции за разрешаване на проблем или извършване на определена дейност. В компютърните науки алгоритмите се използват за широк спектър от операции, от фундаментална математика до сложна обработка на данни.

Един от често срещаните алгоритми, използвани в C, е алгоритъмът за сортиране. Алгоритъмът за сортиране подрежда колекция от елементи в определен ред, например по числа или по азбучен ред.

Има много алгоритми за сортиране, всеки от които има предимства и недостатъци. Най-често срещаните алгоритми за сортиране в C са бързо сортиране, сливане и сортиране.

Една от ключовите характеристики на C е поддръжката на указател. Това позволява ефективно манипулиране на структури от данни като масиви, опашки и т.н. Това го прави подходящ за прилагане на алгоритми, които изискват сложна манипулация на данни, като сортиране и алгоритмично търсене.

Един от известните примери за софтуерна библиотека, реализирана в C, е Standard Template Library (STL). Тази библиотека предоставя голямо разнообразие от алгоритми за задачи като сортиране, търсене и манипулиране на структури от данни.

Характеристики на алгоритъма

Той определя няколко важни характеристики на алгоритъма, включително:

Входове: Алгоритмите трябва да получават входове, които могат да бъдат представени като стойности или данни.Изход: Алгоритъмът трябва да генерира някакъв резултат. Може да е следствие от проблем или решение, предназначено да го реши.Яснота: Алгоритмите трябва да бъдат точно дефинирани, като се използват недвусмислени инструкции, които компютърът или друга система могат да следват недвусмислено.Крайност: Алгоритъмът изисква ограничени стъпки. Това означава, че трябва да се излезе след изпълнение на определен брой команди.Валидност: Алгоритъмът трябва да е валиден. С други думи, той трябва да може да произведе решение на проблема, който алгоритъмът е предназначен да разреши в разумен период от време.Ефикасност:Алгоритъмът трябва да бъде ефективен, което означава, че трябва да може да произведе решение на проблема, който е предназначен да реши, за разумен период от време.Общи:Алгоритъмът трябва да бъде общ, което означава, че може да се прилага към широк кръг от проблеми, вместо да бъде специфичен за един проблем.

Анализ на алгоритъма

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

Анализът на алгоритмите обикновено включва измерване на тяхната времева и пространствена сложност.

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

Има различни начини за анализиране на времевата сложност на алгоритмите, като нотация Big O и Omega. Символът Омега осигурява горна граница за времевата сложност на алгоритъма, докато символът Омега осигурява долна граница.

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

Стабилност:- Това се отнася до способността на алгоритъма да поддържа относителния ред на елементите в набора от данни.Паралелизиране:- Това се отнася до капацитета за паралелно изпълнение на операции в няколко процесора.Мащабируемост:- От друга страна, това се отнася до способността на алгоритъма да обработва големи обеми данни и други входове.

Те включват два вида анализи.

те са:-

1. Предварителен анализ.
2. Заден анализ.

Предварителен анализ

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

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

Заден анализ

Задният анализ, от друга страна, е метод за анализ на алгоритъм, който действително изпълнява алгоритъма и измерва неговата ефективност.

Този подход предоставя по-точна и подробна информация за работата на алгоритъма, но изисква внедряване и изпълнение на алгоритъма.

Сложност на алгоритъма

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

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

те са:-

1. Времеви фактор.
2. Космически фактор.

Времеви фактор

• Времето, което алгоритъмът трябва да изпълни дадена задача, се нарича времева сложност. Обикновено се измерва с броя операции или стъпки, които алгоритъмът трябва да изпълни, за да реши проблем.
• Времевата сложност на алгоритъма е важна, защото определя колко време отнема изпълнението му и може да има значително влияние върху производителността на програмата и системата.
• Времевата сложност на алгоритъм може да бъде изразена с помощта на нотация Big O, начин за изразяване на горна граница на времевата сложност на алгоритъм.
• Алгоритъм с времева сложност O(n) означава, че времето, необходимо за изпълнение на алгоритъма, е право пропорционално на размера на входните данни (n).
• Други често срещани времеви сложности са O(n^2) квадратична сложност и O(log n) логаритмична сложност.

Космически анализ

• От друга страна, пространствената сложност се отнася до количеството памет или място за съхранение, необходимо за изпълнение на алгоритъма.
• Това е важно, защото определя броя на ресурсите, необходими за изпълнение на алгоритми, които могат да повлияят на цялостната производителност на вашето приложение или система.
• Ако пространствената сложност на алгоритъма е O(n), той използва количество памет, което расте линейно с размера на входа.
• Ако алгоритъмът има O(1) пространствена сложност, той използва фиксирано количество памет, независимо от размера на входа.

Как се пише алгоритъм

1. Първо дефинирайте проблема, който искате алгоритъмът да разреши.

Да предположим например, че искаме да напишем алгоритъм за намиране на максималната стойност от списък с числа.

2. Разбийте проблема на по-малки, управляеми стъпки.

• Инициализирайте променливата 'max' до първата стойност в списъка.
• За всяка следваща стойност в списъка сравнете с „max“.
• Ако стойността е по-голяма от „max“, задайте „max“ на тази стойност.
• Продължете да правите това, докато всяка стойност в списъка бъде сравнена.
• Връща крайната „максимална“ стойност.

3. Напишете вашия алгоритъм на псевдокод или език за програмиране.

конвенция за именуване за java

Алгоритъм, написан на псевдокод:

 MAX (list) max = list[0] For i = 1 the length of the list list IF[i] > max max = list[i] End for Maximum return Maximum end 

4. Тествайте алгоритъма си, за да се уверите, че е правилен и ефективен.

Можете да тествате алгоритъма, като въведете различни списъци с числа и проверите дали връща максималната правилна стойност. Можете също така да анализирате времевата сложност на вашия алгоритъм, за да определите колко добре се мащабира за по-големи входове.

Пример:-

Вход: [1, 5, 2, 7, 3]

Резултат: 7.

Обяснение: 7 е максималната стойност в списъка.

5. Оптимизирайте алгоритъма.

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

Основно писане на алгоритми

Пример: - Сумата от две цели числа.

Етап 1 - Първи стъпки

Стъпка 2 - Декларирайте три цели числа a, b, c

Стъпка 3 - Определете стойностите на a и b

Стъпка 4 - Добавете стойностите на a и b

Стъпка 5 - Запазете резултата от стъпка 4 в c

Стъпка 6 - Печат c

Стъпка 7 - Спри се

Тип алгоритми, използвани в езика C.

1. Алгоритми за сортиране

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

Тези алгоритми са полезни в много приложения, тъй като могат да се използват за сортиране на данни с различни размери и типове.

Има различни алгоритми за сортиране.

те са:-

(i) Сортиране на мехурчета: Неусложнен алгоритъм за сортиране, който сравнява близките компоненти многократно и ги изключва, ако не са в ред.

статична ключова дума в java

Алгоритъмът за балонно сортиране е: -

1. Започнете с несортиран списък от елементи.
2. Сравнете първите два елемента в списъка. Ако първият елемент е по-голям от втория елемент, разменете ги.
3. Преминете към следващата двойка елементи и повторете стъпка 2, докато стигнете до края на списъка.
4. За всеки елемент от списъка повторете стъпки 2 и 3 още веднъж. което се нарича пропуски.
5. Повторете стъпки 2-4 за целия списък. Докато повтаряте преминаванията, елементите ще се „издигнат“ до правилната си позиция в сортирания списък.
6. След като преминаването е завършено и не са направени суапове, списъкът се сортира и алгоритъмът може да спре.
7. Връща се окончателният сортиран списък.

(ii) Сортиране на вмъкване : метод за сортиране, който създава сортиран списък един по един отделен елемент чрез поставяне на всеки един на съответното място.

Алгоритъмът за сортиране на вмъкване е: -

1. Инициализирайте празен сортиран списък и несортиран списък на елементите, които трябва да бъдат сортирани.
2. Първият член от несортирания списък трябва да бъде взет и поставен на подходящата позиция в сортирания списък.
3. Повторете стъпка 2 за всеки следващ елемент в несортирания списък.
4. Сравнете текущия елемент с елементите в сортирания списък, като започнете с елемента непосредствено вляво.
5. Разменете двата елемента, ако текущият елемент е по-малък от елемента отляво.
6. Ако текущият елемент е по-голям от елемента отляво, вмъкнете го на правилната му позиция в сортирания списък.
7. Повторете стъпки 4-6 за всеки следващ елемент в несортирания списък.
8. След като всички елементи бъдат обработени, сортираният списък ще съдържа всички елементи в правилния ред.
9. Процесът на сортиране е завършен.

(iii) Сортиране на селекцията : метод за сортиране, който последователно започва сортирания списък с най-малкия детайл от неподредения списък.

Алгоритъмът за сортиране на селекция е: -

1. Започнете, като зададете основния елемент на списъка като min елемент.
2. Повторете през останалите елементи в списъка, като сравнявате всеки един с текущия минимум.
3. Задайте нов минимум, ако се установи, че даден елемент е по-малък от съществуващия.
4. Променете текущия минимум до първия елемент от списъка, когато стигне до края си.
5. За останалата несортирана част от списъка повторете стъпки 2-4, но започнете с втория елемент в списъка (тъй като първият елемент вече е сортиран).
6. Продължете да сортирате списъка по този начин, докато не бъде сортиран.

(iv) Бързо сортиране : Алгоритъм за сортиране разделяй и владей, който избира осев елемент и разделя списъка на подсписъци в зависимост от това дали елементите са по-малко или повече от осевата точка. След това подсписъците се сортират многократно, докато се сортира пълният списък.

Алгоритъмът за бързо сортиране е:

1. Изберете осев елемент от списъка. Това обикновено е първият елемент, но може да бъде и случаен елемент или медианата на списъка.
2. Разделете списъка на два подсписъка: един, съдържащ елементи, по-малки от опорната точка, и един, съдържащ елементи, по-големи от опорната точка.
3. Рекурсивно сортирайте подсписъка, съдържащ елементи, по-малко от опорната точка, като използвате същия процес.
4. Използвайте същата процедура, за да сортирате рекурсивно подсписъка от записи, по-големи от опорната точка.
5. Свържете сортираните подсписъци с основния елемент между тях, за да образувате напълно сортиран списък.
6. Върнете напълно сортирания списък.

(v) Лотът отива : Алгоритъмът за сортиране разделяй и владей разделя списъка на две половини, сортира всяка половина и след това обединява двете половини в сортиран ред.

Алгоритъм за сортиране чрез сливане:

1. Направете два подсписъка от списъка: един с елементи под централната точка и един с елементи над централната точка.
2. Създава нов сортиран подсписък чрез итеративно обединяване на подсписъци, докато съществува само един подсписък. Това ще бъде вашият сортиран списък.
3. Стъпки за обединяване на две поддиректории:-
4. Създайте празен списък за съхранение на сортираните елементи.
5. Сравнява първия елемент от всеки подсписък.
6. Добавя по-малкия елемент към новия списък и го премахва от родителския подсписък.
7. Повторете стъпки 2 и 3, докато списъкът е напълно празен.
8. Добавя останалите елементи от други подсписъци към нов списък.
9. Заменя обединения подсписък с новия сортиран списък.
10. Повторете този процес, докато всички подсписъци се обединят в един сортиран списък.

(vi) Сортиране на купчина : Алгоритъм за сортиране, който сортира елементи, използвайки структура от данни, наречена куп.

Това е алгоритъмът за класификация:

Изградете максимална купчина: Започвайки с първия възел, който не е лист, сравнете всеки възел с неговите дъщерни възли и заменете възлите с най-големия от неговите деца, за да удовлетворите свойството за максимална купчина.Разменете корен с последния елемент: Разменете корена (най-големия елемент) с последния елемент в стека.
1. Подредете останалите елементи. Започвайки от корена, всеки възел се сравнява със своите деца, като възлите се разменят с техните по-големи деца, докато не бъде изпълнено свойството за максимална купчина.
2. Повторете стъпки 2 и 3 с новоподредените елементи, с изключение на последния елемент в правилната позиция.
3. Повторете този процес, докато в стека остане само един елемент. Това вече е сортирано.
Heapify Down: Започвайки от основния възел, той сравнява елементите с неговите дъщерни елементи и разменя с по-големия от двата, докато не бъде изпълнено свойството за максимална купчина.Heapify Up: Започнете с последния елемент в купчината, сравнете го с неговия родител и го разменете с родителя, за да удовлетворите свойството за максимална купчина.

(vii) Сортиране по радикс : Алгоритъм за сортиране, който сортира елементи въз основа на цифрите или цифрите от тяхното двоично представяне.

Алгоритъмът за сортиране по Radix е: -

1. определи колко цифри се съдържат в най-големия елемент на входния списък.
2. Инициализирайте променлива, да речем цифрено място, до 1, което представлява текущото цифрово място.
3. Създайте празен списък за всяка възможна цифрена стойност от 0 до 9.
4. Преминете през входния списък и добавете всеки елемент към подходящия списък въз основа на стойността на текущото място на цифрата.
5. Свържете всички списъци заедно, за да образувате новия списък в реда на списъците с цифри.
6. Умножете digitPlace по 10, за да преминете към следващото място на цифрата.
7. Повторете стъпки 4-6 за всяко място на цифрата, докато не бъдат разгледани всички цифри в най-големия елемент.
8. Окончателният списък ще бъде сортиран във възходящ ред по цифрите на елементите.
9. Връща окончателно сортирания списък.

2. Алгоритми за търсене

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

Има много видове алгоритми за търсене.

Те са:-

(i) Линейно търсене : Основен алгоритъм за търсене, който разглежда всеки елемент в списъка един по един, докато намери желания елемент.

Алгоритъм за линейно търсене: -

1. Дефинирайте входа за алгоритъма: Входът за алгоритъм за линейно търсене е списък от елементи (или масив) и целеви елемент, който търсим.
2. Инициализирайте променлива, наречена „индекс“, на -1: Тази променлива ще се използва за съхраняване на индекса на целевия елемент, ако бъде намерен.
3. Прегледайте списъка с елементи: Започвайки от първия елемент, проверете всеки елемент в списъка един по един.
4. Сравнете настоящия елемент с желания елемент за оценка: Запазете индекса на текущия елемент в променливата индекс и излезте от цикъла, ако модерният елемент и целевият елемент са идентични.
5. Върнете индекса на целевия елемент: След като цикълът завърши, върнете стойността, съхранена в индексната променлива. Ако целевият елемент не бъде намерен, стойността на индекса ще бъде -1.

(ii) Двоично търсене : Алгоритъм за търсене, който работи чрез разделяне на списъка на половини и търсене в рамките на тези половини, е по-вероятно да включи елемента.

Алгоритъм за двоично търсене: -

1. Вход: Сортиран списък от n елемента и целеви елемент x.
2. Инициализиране на променливи: Задайте ниския индекс на 0, високия индекс на n-1 и средния на (нисък+висок)/2.
3. Стартиране на цикъл: Докато ниският индекс е по-малък или равен на високия индекс, повторете следните стъпки.
4. Сравнете средния елемент с x: Ако средният елемент е равен на x, върнете средния индекс.
5. Актуализирайте ниския или високия индекс: Ако x е по-голям от средния елемент, задайте ниския индекс на среден + 1. В противен случай задайте високия индекс на среден - 1.
6. Актуализирайте средния индекс: Mid = (нисък+висок)/2.
7. Край на цикъла: Ако ниският индекс е по-голям от високия индекс, тогава x не е в списъка и алгоритъмът връща грешка.
8. Изход: Индексът на x в списъка или съобщението за грешка.

(iii) Търсене първо в дълбочина : Алгоритъм за търсене, който изследва всеки клон, доколкото е възможно, преди да се обърне.

Следните насоки се прилагат за търсене в дълбочина:

1. изберете началния връх или възел на графиката, с който да започнете.
2. Добавете знак за посещение към първия връх.
3. Директно поставете началния връх в стек.
4. Докато стекът се изпразни, повтаряйте следните действия: -
   • Премахнете горния връх на стека.
   • Маркирайте като посетени и вмъкнете в стека всеки непосетен съсед на изскочения връх.
5. Продължете този процес, докато не бъдат посетени всички върхове в графиката.
6. След като всички върхове бъдат посетени, алгоритъмът е завършен и на графиката се извършва първо търсене в дълбочина.

(iv) Търсене в широчината : Алгоритъм за търсене, който изследва всички съседи на възел, преди да премине към следващото ниво.

Алгоритъмът за търсене в ширина е:

1. Започнете с коренния възел или първоначалното състояние.
2. Добавяне на основния възел към опашка.
3. Проверете дали опашката е празна; ако да, тогава прекратете алгоритъма.
4. Вземете първия елемент от опашката и го маркирайте като посетен.
5. Разширете съвременния възел, като добавите всички негови непосетени съседи към опашката.
6. Докато се намери желаният възел или опашката се изпразни, повторете стъпки от 3 до 5.
7. Върнете пътя от предварителното състояние към целевото състояние, ако целевият възел бъде намерен.
8. Прекратете набора от правила и докладвайте, че състоянието на целта не е идентифицирано, ако опашката е празна.

(v) Интерполационно търсене : Алгоритъм за търсене, който използва стойностите на търсените елементи, за да оцени позицията в индекса.

Важно е масивът да е равномерно разпределен. В противен случай това е алгоритъм.

Работи според очакванията.

Алгоритъмът може да се обобщи по следния начин.

1. Вземете списъка с входни данни и ключовата стойност за търсене.
2. Инициализирайте долните и горните променливи в първия и последния индекс на списъка.
3. Ако долната стойност е по-малка или равна на по-високата стойност, тогава:-
   1. Изчислете очакваното местоположение, като използвате следната формула:
      pos = ниско + ((високо - ниско) / (arr[високо] - arr[ниско])) * (x - arr[ниско]).
   2. Връща позицията, ако очакваната стойност на позицията е ключова стойност.
   3. c) Ако очакваната стойност на позицията е по-малка от ключовата стойност, задайте я по-ниска.
      Позиция + 1.
   4. г) Ако стойността на прогнозната позиция е по-голяма от зададената стойност на ключа, позиция - 1 нагоре.
4. Ако стойността на ключа не е намерена, върнете -1, за да посочите, че стойността не е в списъка.

(vi) Прескачащо търсене : Метод за търсене, който обикаля списъка на стъпки с постоянна дължина, докато намери съответния елемент или установи, че той вече не присъства.

Алгоритъмът за търсене на скок е както следва:

1. Първо, задайте размера на скока на корен квадратен от броя на елементите на масива.
2. Задава променлива с име 'current' на първия елемент от масива.
3. Преминава през масива, като скача по размер на скока, докато увеличава променлива, наречена „скок“.
4. Преминете към следващия скок, ако съществуващият елемент е по-малък от желания елемент.
5. Ако текущият елемент е по-голям от целевия елемент, извършете линейно търсене между текущия елемент и предишния скок, за да намерите целевия елемент.
6. Ако целевият елемент не е намерен в масива, той връща -1, за да покаже, че не е в масива.
7. Ако елементът бъде намерен, той връща индекса на елемента в масива.

3. Графични алгоритми

Поддръжката на C за указатели и структури от данни като масиви и свързани списъци го прави подходящ за прилагане на алгоритми, които манипулират графики, като например намиране на най-краткия път между два възела в графика.

Има различни видове графични алгоритми.

те са:-

Алгоритъмът на Дейкстра: Алгоритъм, който намира най-краткия път между два възела в графика чрез непрекъснато актуализиране на най-късото разстояние от всеки възел.Алгоритъм A*: Метод, който непрекъснато актуализира най-краткия курс до всеки възел в графика, за да определи най-краткия маршрут между тях.Алгоритъмът на Прим: Подход за намиране на най-малкото обхващащо дърво на претеглената свързана графа.Kruskal's algorithm: Подход за идентифициране на най-ниското обхващащо дърво на свързания претеглен график.Алгоритъм на Белман-Форд: Алгоритъм, който, дори когато графиката има отрицателни тегла на ръба, показва най-краткия път между конкретен възел на захранване и всеки друг възел в мрежата.

4. Криптографски алгоритми

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

Има различни видове алгоритми за криптиране.

валидни идентификатори в java

Те са:-

Хеш алгоритми: Тези алгоритми произвеждат изходи с фиксиран размер (хеш) от входове с произволен размер. Примерите включват MD5, SHA-1 и SHA-2.Симетрични ключови алгоритми: Стъпките на криптиране и декриптиране в такива алгоритми използват един и същ частен ключ. AES, DES и Blowfish са няколко примера.Асиметрични ключови алгоритми: Публичен ключ и непубличен ключ се използват от тези методи като отделни ключове за криптиране и декриптиране. Някои примери включват RSA, ECC и DSA.Алгоритми за обмен на ключове: Тези алгоритми позволяват на две страни да обменят ключове по несигурен канал по сигурен начин. Например можем да споменем Дифи-Хелман и Елиптична крива на Дифи-Хелман.

Предимства на алгоритъма

Алгоритмите имат много предимства.

те са:-

Бързина и ефективност: Алгоритмите могат да обработват големи количества данни бързо и точно, което ги прави полезни за задачи, които отнемат твърде много време или са податливи на грешки, за да бъдат изпълнени от хората.Последователност: Алгоритмите следват набор от предварително определени указания. Може да доведе до последователни резултати, без да се влияе от лични пристрастия и емоции.Автоматизация: Алгоритмите могат да изпълняват задачи автоматично, оставяйки хората свободни да се съсредоточат върху по-сложни или творчески задачи.Повишена точност: Алгоритмите често могат да постигнат по-високи нива на точност от хората, особено когато работят с големи количества данни.По-добро вземане на решения: Алгоритмите ни помагат да вземаме по-информирани и обективни решения чрез анализиране на данни и идентифициране на модели и тенденции, които не са лесно видими за хората.Мащабируемост: Алгоритмите могат лесно да бъдат мащабирани нагоре или надолу, за да отговорят на променящите се изисквания и натоварвания.

Недостатъци на алгоритъма

Алгоритмите са много полезни за програмиране, но алгоритмите имат недостатъци.

те са:-

Ограничен обхват: Алгоритмите могат да решават само проблеми в своя обхват и може да не са в състояние да решават сложни или абстрактни проблеми.Пристрастие: Алгоритмите могат да поддържат и засилват отклоненията в данните, използвани за обучение, което води до несправедливи резултати.Недостатъчна прозрачност: Много алгоритми прикриват процеса, чрез който стигат до своите заключения. Това може да затрудни обмислянето или проверката на резултатите.Разчитане на точността на данните:Коректността на набора от правила е силно зависима от фиността и приложимостта на данните, използвани в инструкцията. Неточни или неточни ефекти може да са резултат от грешни данни.сдържана адаптивност:Алгоритмите са проектирани да следват указанията и няма да се адаптират към променящите се обстоятелства и условия.