Нужны ли программисту алгоритмы?
Прежде всего поймем, что такое алгоритм. Неформально Кармен определяет алгоритм как строго определённую процедуру, которая принимает одно или несколько значений как ввод, и возвращает одно или несколько значений как результат. Таким образом, фактически любой код, который что-то делает, является алгоритмом. Получается, что вопрос «нужны ли программисту алгоритмы» можно перевести как «нужно ли программисту уметь писать код». А точнее «нужно ли программисту в отрасли Х знать N-ые алгоритмы».
Но есть три характеристики алгоритмов, которые каждый программист должен понимать:
1. Определенность - описывает, что каждый шаг точно определен.
2. Эффективная вычислимость - описывает, что каждый шаг может быть выполнен компьютером.
3. Конечность - описывает, что процедура завершается.
Для решения задачи обычно существует множество различных алгоритмов. Один алгоритм может потребовать наименьшего количества шагов. Другой алгоритм может допускать одновременное выполнение некоторых шагов. Компьютер, который позволяет выполнять несколько действий одновременно, часто может решить проблему за меньшее время, даже если общее количество выполняемых шагов увеличилось.
Прежде всего поймем, что такое алгоритм. Неформально Кармен определяет алгоритм как строго определённую процедуру, которая принимает одно или несколько значений как ввод, и возвращает одно или несколько значений как результат. Таким образом, фактически любой код, который что-то делает, является алгоритмом. Получается, что вопрос «нужны ли программисту алгоритмы» можно перевести как «нужно ли программисту уметь писать код». А точнее «нужно ли программисту в отрасли Х знать N-ые алгоритмы».
Но есть три характеристики алгоритмов, которые каждый программист должен понимать:
1. Определенность - описывает, что каждый шаг точно определен.
2. Эффективная вычислимость - описывает, что каждый шаг может быть выполнен компьютером.
3. Конечность - описывает, что процедура завершается.
Для решения задачи обычно существует множество различных алгоритмов. Один алгоритм может потребовать наименьшего количества шагов. Другой алгоритм может допускать одновременное выполнение некоторых шагов. Компьютер, который позволяет выполнять несколько действий одновременно, часто может решить проблему за меньшее время, даже если общее количество выполняемых шагов увеличилось.
Статическая и динамическая типизации
Отличие статической типизации от динамической — это то, что все проверки типов выполняются на этапе компиляции, а не на этапе выполнения.
Обсуждая эту тему, люди обычно делятся на две группы: одни, кто считает, что статическая типизация слишком ограничена, другие, что динамически типизированные языки — это игра с огнем. Но так ли это?
Рассмотрим преимущества этих двух типизаций
Статическая (C, Java, C#):
⁃ Проверки типов происходят только один раз — на этапе компиляции.
⁃ Скорость выполнения.
⁃ При некоторых дополнительных условиях, позволяет обнаруживать потенциальные ошибки уже на этапе компиляции.
⁃ Ускорение разработки при поддержке IDE
Динамическая (Python, JavaScript, Ruby):
⁃ Простота создания универсальных коллекций
⁃ Удобство описания обобщенных алгоритмов.
⁃ Языки с динамической типизацией обычно очень хороши для того, чтобы начать программировать
Отличие статической типизации от динамической — это то, что все проверки типов выполняются на этапе компиляции, а не на этапе выполнения.
Обсуждая эту тему, люди обычно делятся на две группы: одни, кто считает, что статическая типизация слишком ограничена, другие, что динамически типизированные языки — это игра с огнем. Но так ли это?
Рассмотрим преимущества этих двух типизаций
Статическая (C, Java, C#):
⁃ Проверки типов происходят только один раз — на этапе компиляции.
⁃ Скорость выполнения.
⁃ При некоторых дополнительных условиях, позволяет обнаруживать потенциальные ошибки уже на этапе компиляции.
⁃ Ускорение разработки при поддержке IDE
Динамическая (Python, JavaScript, Ruby):
⁃ Простота создания универсальных коллекций
⁃ Удобство описания обобщенных алгоритмов.
⁃ Языки с динамической типизацией обычно очень хороши для того, чтобы начать программировать
Машина Тьюринга (МТ) и какое отношение она имеет к программированию
МТ — это модель для формализации понятия алгоритма.
МТ состоит из бесконечной ленты, разделенной на ячейки и управляющего устройства.
Это устройство может перемещаться влево и вправо, читать и писать различные символы определенного алфавита с конечным числом символов.
Оно работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной МТ. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния МТ могут быть помечены как терминальные, и переход в любое из них означает конец работы, то есть, остановку алгоритма.
В общем, МТ - способ определить некоторый класс алгоритмов:
⁃ некоторые задачи можно решить конечным автоматом;
⁃ для некоторых потребуется конечный автомат со стековой памятью;
⁃ для других достаточно МТ
МТ — это модель для формализации понятия алгоритма.
МТ состоит из бесконечной ленты, разделенной на ячейки и управляющего устройства.
Это устройство может перемещаться влево и вправо, читать и писать различные символы определенного алфавита с конечным числом символов.
Оно работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной МТ. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния МТ могут быть помечены как терминальные, и переход в любое из них означает конец работы, то есть, остановку алгоритма.
В общем, МТ - способ определить некоторый класс алгоритмов:
⁃ некоторые задачи можно решить конечным автоматом;
⁃ для некоторых потребуется конечный автомат со стековой памятью;
⁃ для других достаточно МТ
Алгоритм, который каждый программист должен знать!
Бинарный поиск - это алгоритм поиска элемента в отсортированном массиве, который возвращает индекс этого элемента в данном массиве.
Представьте, у вас есть массив, где находится миллион чисел, и вы хотите найти какое-то конкретное и извлечь его индекс.
Используя линейный поиск, вы бы начали сначала и на каждой итерации последовательно сравнивали бы искомое значение со значениями в массиве. И если вы например ищете число 3, то вам крупно повезло и вам понадобится всего 3 итерации, но в худшем случае, когда вы ищите число миллион, вам придется перебирать весь массив, следовательно это миллион итераций (очень много).
Но если использовать бинарный поиск, то все становится проще. Нам нужно поделить массив пополам и сравнить искомое значение с серединным, если оно меньше, то мы отбрасываем вторую половину массива и ищем уже только в первой. И так далее, пока не найдем искомое значение.
При бинарном поиске каждый раз исключается половина чисел.
Сложность бинарного поиска: логарифмическая
Бинарный поиск - это алгоритм поиска элемента в отсортированном массиве, который возвращает индекс этого элемента в данном массиве.
Представьте, у вас есть массив, где находится миллион чисел, и вы хотите найти какое-то конкретное и извлечь его индекс.
Используя линейный поиск, вы бы начали сначала и на каждой итерации последовательно сравнивали бы искомое значение со значениями в массиве. И если вы например ищете число 3, то вам крупно повезло и вам понадобится всего 3 итерации, но в худшем случае, когда вы ищите число миллион, вам придется перебирать весь массив, следовательно это миллион итераций (очень много).
Но если использовать бинарный поиск, то все становится проще. Нам нужно поделить массив пополам и сравнить искомое значение с серединным, если оно меньше, то мы отбрасываем вторую половину массива и ищем уже только в первой. И так далее, пока не найдем искомое значение.
При бинарном поиске каждый раз исключается половина чисел.
Сложность бинарного поиска: логарифмическая
Память компьютера
Память - компонент компьютера, способный хранить в себе различную информацию (под информации можно понимать буквально все: программы, картинки, текст и тд), которая представляется в двоичном виде.
Иерархия памяти (от самой маленькой, но быстрой до самой большой, но медленной)
1. регистры - ячейки памяти, которые находятся на самом процессоре
2. кэш-память - хранилище для часто используемых процессором данных
3. оперативная память - именно та память, в которой находятся программы, выполняющиеся данный момент времени.
4. внешняя память - флешки, жесткие диски и тд.
Память - компонент компьютера, способный хранить в себе различную информацию (под информации можно понимать буквально все: программы, картинки, текст и тд), которая представляется в двоичном виде.
Иерархия памяти (от самой маленькой, но быстрой до самой большой, но медленной)
1. регистры - ячейки памяти, которые находятся на самом процессоре
2. кэш-память - хранилище для часто используемых процессором данных
3. оперативная память - именно та память, в которой находятся программы, выполняющиеся данный момент времени.
4. внешняя память - флешки, жесткие диски и тд.
Оперативная память. Бит и байт
Представляет собой огромный набор ячеек.
Одна ячейка может хранить в себе один бит. Бит - минимальная единица хранения информации, которая может быть выражена 0 или 1 (что является абстракцией над наличием или отсутствием тока)
Ячейки (биты) объединяются в группы по 8 штук и получаются байты. Дело в том, что процессор может обращаться только к какому-то определенному байту в памяти (байт - минимальная ячейка адресации)
В каждой группе ячеек, самый правый бит называется младшим битом, а самый левый — страшим.
Какая такая группа имеет свой адрес, по которому процессор может к ней обращаться.
Представляет собой огромный набор ячеек.
Одна ячейка может хранить в себе один бит. Бит - минимальная единица хранения информации, которая может быть выражена 0 или 1 (что является абстракцией над наличием или отсутствием тока)
Ячейки (биты) объединяются в группы по 8 штук и получаются байты. Дело в том, что процессор может обращаться только к какому-то определенному байту в памяти (байт - минимальная ячейка адресации)
В каждой группе ячеек, самый правый бит называется младшим битом, а самый левый — страшим.
Какая такая группа имеет свой адрес, по которому процессор может к ней обращаться.
Структура данных — массив
Массив - это структура однотипных данных, расположенная в памяти одним неразрывным блоком.
Каждая переменная в массиве является самостоятельной единицей и называется элементом. Каждый элемент имеет свою позицию — свой индекс.
Нумерация индексов начинается с 0, а не с 1. Иногда, начинающих программистов это вводит в ступор, но тем не менее выбор нулевой начальной позиции упрощает написание кода по работе с массивами, поэтому разработчики остановились на этом варианте.
Работая с массивом вы заранее знаете адрес каждого элемента, поэтому они прекрасно подходят для чтения в произвольных позициях, так как обращение к любому элементу происходит мгновенно.
Время выполнения основных операций:
Чтение - O(1)
Вставка - O(n)
Удаление - O(n)
Массив - это структура однотипных данных, расположенная в памяти одним неразрывным блоком.
Каждая переменная в массиве является самостоятельной единицей и называется элементом. Каждый элемент имеет свою позицию — свой индекс.
Нумерация индексов начинается с 0, а не с 1. Иногда, начинающих программистов это вводит в ступор, но тем не менее выбор нулевой начальной позиции упрощает написание кода по работе с массивами, поэтому разработчики остановились на этом варианте.
Работая с массивом вы заранее знаете адрес каждого элемента, поэтому они прекрасно подходят для чтения в произвольных позициях, так как обращение к любому элементу происходит мгновенно.
Время выполнения основных операций:
Чтение - O(1)
Вставка - O(n)
Удаление - O(n)
Алгоритмы сортировок
Алгоритмы сортировок это самая частая тема, которую спрашивают на собеседованиях. Сейчас мы рассмотрим, какие есть и их сложность по времени. Подробно как они работают, рассмотрим в будущих постах.
1. Сортировка пузырьком
Худшее время -
2. Сортировка перемешиванием
Худшее время -
3. Сортировка расческой
Худшее время -
4. Сортировка вставками
Худшее время -
5. Сортировка выбором
Худшее время -
6. Быстрая сортировка
Худшее время -
7. Сортировка слиянием
Худшее время -
8. Пирамидальная сортировка
Худшее время -
Алгоритмы сортировок это самая частая тема, которую спрашивают на собеседованиях. Сейчас мы рассмотрим, какие есть и их сложность по времени. Подробно как они работают, рассмотрим в будущих постах.
1. Сортировка пузырьком
Худшее время -
O(n^2) | Лучшее время - O(n)2. Сортировка перемешиванием
Худшее время -
O(n^2) | Лучшее время - O(n)3. Сортировка расческой
Худшее время -
O(n^2) | Лучшее время - O(n log n)4. Сортировка вставками
Худшее время -
O(n^2) | Лучшее время - O(n) или O(1)5. Сортировка выбором
Худшее время -
O(n^2) | Лучшее время - O(n^2)6. Быстрая сортировка
Худшее время -
O(n^2) | Лучшее время - O(n) 7. Сортировка слиянием
Худшее время -
O(n log n) | Лучшее время - O(n log n) 8. Пирамидальная сортировка
Худшее время -
O(n log n) | Лучшее время - O(n log n) или O(n)Динамическая структура данных — Односвязный список
Односвязный список - это динамическая структура данных, состоящая из узлов. Каждый узел будет иметь некоторое значение и указатель на следующий узел.
При использовании связного списка элементы размещаются где угодно в памяти. И так как в каждом элементе хранится адрес следующего элемента списка, то набор произвольных адресов памяти объединяется в цепочку.
Связные списки очень хорошо справляется со вставкой. Чтобы добавить новый элемент в список, просто разместите его по любому адресу и сохраните этот адрес в предыдущем элементе. Со связными списками ничего в памяти перемещать не нужно.
Время выполнения основных операций:
Чтение -
Вставка -
Удаление -
Односвязный список - это динамическая структура данных, состоящая из узлов. Каждый узел будет иметь некоторое значение и указатель на следующий узел.
При использовании связного списка элементы размещаются где угодно в памяти. И так как в каждом элементе хранится адрес следующего элемента списка, то набор произвольных адресов памяти объединяется в цепочку.
Связные списки очень хорошо справляется со вставкой. Чтобы добавить новый элемент в список, просто разместите его по любому адресу и сохраните этот адрес в предыдущем элементе. Со связными списками ничего в памяти перемещать не нужно.
Время выполнения основных операций:
Чтение -
O(n)Вставка -
O(1)Удаление -
O(1)Сетевая модель OSIThe Open Systems Interconnection model - сетевая модель стека сетевых протоколов OSI/ISO. Посредством данной модели различные сетевые устройства могут взаимодействовать друг с другом. Модель определяет различные уровни взаимодействия систем.
Выделяют 7 уровней взаимодействия:1. Физический — работа со средой передачи, сигналами и двоичными данными
2. Канальный — физическая адресация
3. Сетевой — определение маршрута и логическая адресация
4. Транспортный — прямая связь между конечными пунктами и надёжность
5. Сеансовый — управление сеансом связи
6. Представления — представление и шифрование данных
7. Прикладной — доступ к сетевым службам
Сортировка пузырьком
Один из самых известных и простых алгоритмов сортировки. Его суть заключается в просматривании значений соседних элементов, если предыдущий элемент оказывается больше последующего, то меняем их местами.
Этот алгоритм почти не применяется на практике из-за низкой эффективности. Однако на нем основаны многие другие методы.
Сложность по времени:
Худшее время:
Среднее время:
Лучшее время:
Затраты на память:
Один из самых известных и простых алгоритмов сортировки. Его суть заключается в просматривании значений соседних элементов, если предыдущий элемент оказывается больше последующего, то меняем их местами.
Этот алгоритм почти не применяется на практике из-за низкой эффективности. Однако на нем основаны многие другие методы.
Сложность по времени:
Худшее время:
O(n^2)Среднее время:
O(n^2)Лучшее время:
O(n)Затраты на память:
O(1)Быстрая сортировка
Ей уже 60 лет, но она до сих пор работает быстро.
За основу, была взята классическая сортировка пузырьком и преобразована таким образом:
1. на очередном шаге выбирается опорный элемент — им может быть любой элемент массива
2. Все остальные элементы массива сравниваются с опорным и те, которые меньше него, уставляться слева от него, а которые больше или равны — справа
3. Далее для двух получившихся блоков массива выполняется пункт 1 и 2.
Особенность алгоритма в том, что так как в пункте 3 мы разбиваем массив на два и для каждой части делаем то же самое, и так снова и снова, то это значит, что в нём используется рекурсия.
Сложность по времени:
Худшее время:
Среднее время:
Лучшее время:
Затраты на память:
Ей уже 60 лет, но она до сих пор работает быстро.
За основу, была взята классическая сортировка пузырьком и преобразована таким образом:
1. на очередном шаге выбирается опорный элемент — им может быть любой элемент массива
2. Все остальные элементы массива сравниваются с опорным и те, которые меньше него, уставляться слева от него, а которые больше или равны — справа
3. Далее для двух получившихся блоков массива выполняется пункт 1 и 2.
Особенность алгоритма в том, что так как в пункте 3 мы разбиваем массив на два и для каждой части делаем то же самое, и так снова и снова, то это значит, что в нём используется рекурсия.
Сложность по времени:
Худшее время:
O(n^2)Среднее время:
O(n log n)Лучшее время:
O(n)Затраты на память:
O(n)