Computer Science

Алгоритмы сортировок Алгоритмы сортировок это самая частая тема, которую спрашивают на собеседованиях. Сейчас мы рассмотрим, какие есть и их сложность по времени. Подробно как они работают, рассмотрим в будущих постах.  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)

Структура данных — массив Массив - это структура однотипных данных, расположенная в памяти одним неразрывным блоком. Каждая переменная в массиве является самостоятельной единицей и называется элементом. Каждый элемент имеет свою позицию — свой индекс. Нумерация индексов начинается с 0, а не с 1. Иногда, начинающих программистов это вводит в ступор, но тем не менее выбор нулевой начальной позиции упрощает написание кода по работе с массивами, поэтому разработчики остановились на этом варианте. Работая с массивом вы заранее знаете адрес каждого элемента, поэтому они прекрасно подходят для чтения в произвольных позициях, так как обращение к любому элементу происходит мгновенно. Время выполнения основных операций: Чтение - O(1) Вставка - O(n) Удаление - O(n)

Из чего состоит оперативная память (ОП) Вся оперативная память делится на СТЕК (STACK) и КУЧУ (HEAP). Стек - это отведенная область памяти, где хранятся временные данные. Благодаря ему становится возможно вызывать подпрограммы, они же функции. За стеком располагается весь остальной код, который есть в ОП По другому его называют аппаратным стеком, потому что помимо него, стек еще является структурой данных Куча - это область памяти, где находятся все работающие на данный момент программы (включая ОС). Все данные в куче располагаются линейно в строну увеличения адресов. В стеке же все наоборот, он растет в сторону уменьшения адресов. Это необходимо, для того чтобы стек не затирал данные, которые идут за ним, в случае своего переполнения.

Оперативная память. Бит и байт Представляет собой огромный набор ячеек. Одна ячейка может хранить в себе один бит. Бит - минимальная единица хранения информации, которая может быть выражена 0 или 1 (что является абстракцией над наличием или отсутствием тока) Ячейки (биты) объединяются в группы по 8 штук и получаются байты. Дело в том, что процессор может обращаться только к какому-то определенному байту в памяти (байт - минимальная ячейка адресации) В каждой группе ячеек, самый правый бит называется младшим битом, а самый левый — страшим. Какая такая группа имеет свой адрес, по которому процессор может к ней обращаться.

Память компьютера Память - компонент компьютера, способный хранить в себе различную информацию (под информации можно понимать буквально все: программы, картинки, текст и тд), которая представляется в двоичном виде. Иерархия памяти (от самой маленькой, но быстрой до самой большой, но медленной) 1. регистры - ячейки памяти, которые находятся на самом процессоре 2. кэш-память - хранилище для часто используемых процессором данных 3. оперативная память - именно та память, в которой находятся программы, выполняющиеся данный момент времени. 4. внешняя память - флешки, жесткие диски и тд.

Алгоритм, который каждый программист должен знать! Бинарный поиск - это алгоритм поиска элемента в отсортированном массиве, который возвращает индекс этого элемента в данном массиве. Представьте, у вас есть массив, где находится миллион чисел, и вы хотите найти какое-то конкретное и извлечь его индекс. Используя линейный поиск, вы бы начали сначала и на каждой итерации последовательно сравнивали бы искомое значение со значениями в массиве. И если вы например ищете число 3, то вам крупно повезло и вам понадобится всего 3 итерации, но в худшем случае, когда вы ищите число миллион, вам придется перебирать весь массив, следовательно это миллион итераций (очень много). Но если использовать бинарный поиск, то все становится проще. Нам нужно поделить массив пополам и сравнить искомое значение с серединным, если оно меньше, то мы отбрасываем вторую половину массива и ищем уже только в первой. И так далее, пока не найдем искомое значение. При бинарном поиске каждый раз исключается половина чисел. Сложность бинарного поиска: логарифмическая

Машина Тьюринга (МТ) и какое отношение она имеет к программированию МТ — это модель для формализации понятия алгоритма. МТ состоит из бесконечной ленты, разделенной на ячейки и управляющего устройства. Это устройство может перемещаться влево и вправо, читать и писать различные символы определенного алфавита с конечным числом символов. Оно работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной МТ. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния МТ могут быть помечены как терминальные, и переход в любое из них означает конец работы, то есть, остановку алгоритма. В общем, МТ - способ определить некоторый класс алгоритмов: ⁃ некоторые задачи можно решить конечным автоматом; ⁃ для некоторых потребуется конечный автомат со стековой памятью; ⁃ для других достаточно МТ

Статическая и динамическая типизации Отличие статической типизации от динамической — это то, что все проверки типов выполняются на этапе компиляции, а не на этапе выполнения. Обсуждая эту тему, люди обычно делятся на две группы: одни, кто считает, что статическая типизация слишком ограничена, другие, что динамически типизированные языки — это игра с огнем. Но так ли это? Рассмотрим преимущества этих двух типизаций Статическая (C, Java, C#): ⁃ Проверки типов происходят только один раз — на этапе компиляции. ⁃ Скорость выполнения. ⁃ При некоторых дополнительных условиях, позволяет обнаруживать потенциальные ошибки уже на этапе компиляции. ⁃ Ускорение разработки при поддержке IDE Динамическая (Python, JavaScript, Ruby): ⁃ Простота создания универсальных коллекций ⁃ Удобство описания обобщенных алгоритмов. ⁃ Языки с динамической типизацией обычно очень хороши для того, чтобы начать программировать

Нужны ли программисту алгоритмы? Прежде всего поймем, что такое алгоритм. Неформально Кармен определяет алгоритм как строго определённую процедуру, которая принимает одно или несколько значений как ввод, и возвращает одно или несколько значений как результат. Таким образом, фактически любой код, который что-то делает, является алгоритмом. Получается, что вопрос «нужны ли программисту алгоритмы» можно перевести как «нужно ли программисту уметь писать код». А точнее «нужно ли программисту в отрасли Х знать N-ые алгоритмы». Но есть три характеристики алгоритмов, которые каждый программист должен понимать: 1. Определенность - описывает, что каждый шаг точно определен. 2. Эффективная вычислимость - описывает, что каждый шаг может быть выполнен компьютером. 3. Конечность - описывает, что процедура завершается. Для решения задачи обычно существует множество различных алгоритмов. Один алгоритм может потребовать наименьшего количества шагов. Другой алгоритм может допускать одновременное выполнение некоторых шагов. Компьютер, который позволяет выполнять несколько действий одновременно, часто может решить проблему за меньшее время, даже если общее количество выполняемых шагов увеличилось.