Алгоритми и Комплексност

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Која од следниве функции проверува дали едносмерниот низ е со дупликати?

sort_array

insertion_sort

check_uniqueness

has_duplicates (correct)

Што означува терминот 'бит'?

Основна единица на информација (correct)

Примената на алгоритам

Основен тип на податок

Должина на низата

Кое од следниве операции не е битовата операција?

XOR

AND

AVG (correct)

Која од следниве функции е правилно имплементирана?

has_duplicates Signup and view all the answers

Што е потребно да се знае за алгоритмите за манипулација со битови?

Само основите Signup and view all the answers

Која од следниве тврденија за битовата манипулација е точна?

Изведува операции на индивидуални битови Signup and view all the answers

Кое од следниве е правилно за анализа на времетраење на алгоритмите?

Вклучува и просторна сложеност Signup and view all the answers

Кој процес му овозможува на компјутерот да обработува информации на најниско ниво?

Битова манипулација Signup and view all the answers

Кој оператор се користи за добивање на комплемент на бинарен број?

Bitwise NOT оператор Signup and view all the answers

Што прави операторот за лево поместување (<<) во битовите?

Поместува сите битови на лево Signup and view all the answers

Каква е улогата на XOR операторот во проверка на интегритет на податоци?

Тој потврдува дали файлот не е оштетен Signup and view all the answers

Како можете да поставите бит на позиција n во бројот 'num'?

Користејќи OR оператор Signup and view all the answers

Што значи побитна операција во контекстот на енкрипција на податоци?

Криптирање и компресија на податоци Signup and view all the answers

Која од следниве оператори се смета за битов логички оператор?

AND (&) Signup and view all the answers

Што ќе биде резултатот од операцијата X = 7 и Y = 4 со битов AND оператор?

3 Signup and view all the answers

Кој од следниве изрази претставува битов XOR оператор?

X ^ Y Signup and view all the answers

Која од следните информации е точна за битовата логичка единица (ALU)?

ALU извршува математички операции. Signup and view all the answers

Која од следните операции ќе резултира во 7 ако примените битов OR оператор на 7 и 4?

7 Signup and view all the answers

Кои од следниве оператори работат на индивидуалните битовите на битните шаблони?

Битовите оператори Signup and view all the answers

Која е основната предност на битовите алгоритми во однос на регуларните аритметички операции?

Тие работат со бинарното претставување на податоците. Signup and view all the answers

Каква е функцијата на операторот NOT (~)?

Превртува сите битови на дадениот број. Signup and view all the answers

Study Notes

Задача на денот 1

Функцијата has_duplicates(arr) ја проверува дали даден низ arr содржи дубликати.
Се пресметува должината на низот n = len(arr).
Внатрешен циклус се користи за итерирање низ низот.
Внатрешен циклус се користи за споредба на елементите од низот.
Ако се најде пар со еднакви елементи, функцијата ја враќа вредноста True.
Доколку не се наоѓаат дубликати, функцијата ја враќа False.

Задача на денот 2

Функцијата insertion_sort(arr) сортира даден низ arr со помош на метод на вметнување.
Овој метод ја вметнува вредноста на секој елемент на соодветното место во сортираниот дел на низот.
Циклусот се користи за итерирање низ несортираниот дел на низот.
Вредноста на тековниот елемент се чува во променливата key.
Елементи се споредуваат со key.
Кога key е помалку од елементот на лево, елементите се поместуваат на десно, key се вметнува на соодветното место.
Низот се враќа сортиран.

Темата е посветена на алгоритмите.
Посебно се фокусира на битови алгоритми.

Извадок од "Счупување на интервјуто за кодирање"

Google обрнува внимание на дизајнирање на скалабилни системи.
Имплементирање на скалабилност и ограничувања на меморијата.
Постојат многу прашања за манипулација на битови.
Интервјуерите нудат повратни информации, кои се проследуваат до комисијата за наем.
Комисијата за наем дава препораки за одлука.

Извадок од "Счупување на интервјуто за кодирање"

Наведени се основни податоци:
Листи од поврзани елементи
Бинарни дрвја
Трии
Пребарување внатре во низи
Брзо сортирање, сортирање со спојување, е.т.ц.
Битова манипулација.

Битови

Битот е основна единица од информации.
Може да има вредности 0 или 1.
Обично се користи децималната база за претставување на броевите, но други системи се корисни како бинарниот.

Манипулирање на битови

Компјутерите ракуваат со нули и единици (битови).
Битовите се основни елементи во компјутерскиот систем.
Алгоритмите за манипулирање на битовете се важни.

Битови алгоритми

Битови алгоритмите се однесуваат на работа со битовите како индивиддни елементи или групи во податочниот простор.
Тие користат битови операции за манипулирање и добивање информации.

Битови алгоритми - Ефикасност

Битовите алгоритми се побрзи и користат помалку меморија од редовните аритметички операции.
Ова се должи на директната работа со битова претставата.

Битови оператори

Ова се оператори за манипулирање на битови.
Подобруваат ефикасност во програмите.

Битова оператор табела на вистина

Табелата покажува како различни битови оператори работат со битови.

Битовски AND оператор (&)

Оператор & (AND) се користи со битови, проследувајќи правилото дека само ако два битови се 1, rezult е 1; во спротивно, тоа е 0.
Битовите се изразуваат во бинарниот.

Пример - Код

a = 7 и b = 4.
Извршените операции со &, дава резултат од 4.

Битовски OR оператор (|)

Оператор | (OR) ги споредува битовите. Ако било кој од битовите е 1,, резултатот е 1.

Битовски XOR оператор (^)

Оператор ^ (XOR) враќа 1 ако битовите се различни. Ако сушта битовите се еднакви, резултатот е 0.

Битовски NOT оператор (~)

Оператор ~ (NOT) е уникатен оператор што работи на единечен бит.
Секој бит е инвертиран (0 станува 1, а 1 станува 0).

Лево поместување (<<)

Левото поместување ја поместува вредноста на битовите надесно.
Заполнува нули во празните позиции.

Десно поместување (>>)

Десното поместување го поместува вредноста на битовите налево.
Обично се користи нула за полнење на празни позиции.

Примена на битовски оператори

Се користат за подобрување на вградените системи.
Овозможува проверка на интегритетот на податоците за време на пренесување.
Се користат во криптографијата и компресијата на податоци.

Практични проблеми на битови алгоритми

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

Како да се постави бит во число

Користење на OR (|) оператор за поставување на бит во одредена позиција.
Лево поместување на 1 за итерирање низ битовите.

Како да се исклучи/исчисти бит во число

Користење на AND (&) оператор за исклучување/исчистување бит во одредена позиција.
Битовски NOT (~) оператор се користи за инвертирање на бита.

Смена на бит на nth позиција

Оператор XOR (^) може да го смени битот на nth позиција.

Дополнително читање и вежби

"Кракaње на интервјуто за кодирање" - глава 5 (постои како додатна литература, за проучување).

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Овој квиз ја испитува вашата разбирливост за алгоритмите за проверка на дубликати и методот на вметнување при сортирање на низи. Проверете ја вашата способност да разбиете сложени алгоритми и нивната имплементација. Подгответе се за предизвиците на алгоритамското размислување!

Алгоритми и Комплексност - Дупликати и Сортирање

Choose a study mode