Привет! Меня зовут Гаганвир Сингх, и сейчас я учусь на втором курсе разработки программного обеспечения в Университете Читкара. Осознавая важность и трудности освоения Структур данных и алгоритмов (DSA), я решил записать свое путешествие по этому сложному предмету. В этом блоге я расскажу о своем личном опыте, препятствиях, с которыми я столкнулся, и бесценных уроках, которые я усвоил на этом пути. Моя основная мотивация? Помочь таким студентам, как я, со всех уголков земного шара, с большей легкостью ориентироваться в огромном море DSA. Итак, независимо от того, начинаете ли вы или ищете дополнительную информацию, я надеюсь, что мое путешествие прольет свет на ваше.
Фон:
Прежде чем погрузиться в суть моего путешествия по DSA, давайте совершим краткую прогулку по воспоминаниям. На первом году обучения в Университете Читкара я познакомился с несколькими языками программирования, включая C++ и C#. Больше всего меня поразила красота объектно-ориентированного программирования (ООП) и то, как оно упрощает сложные проблемы. По мере продвижения вперед важно отметить, что концепции DSA, которыми я поделюсь, в основном демонстрируются с использованием языка C#. Я думаю, что его простота и адаптируемость делают его идеальным для деконструкции проблем DSA.
Первая неделя (Погружение в основы):
Когда я впервые пришёл на занятия по DSA, первая неделя послужила мне мягким введением в некоторые основополагающие принципы программирования. Мы освежили наши знания об объектно-ориентированном программировании (ООП), сосредоточив внимание на его четырех основных концепциях.
1. Абстракция. Думайте об абстракции как об искусстве скрывать сложность, демонстрируя только самое важное. Представьте себе свой ноутбук: вам не нужно знать его внутреннюю работу, чтобы им пользоваться. Вам просто нужны кнопки, которые представляют собой абстрактную версию всего сложного механизма внутри.
2. Инкапсуляция. Инкапсуляция подобна защитному пузырю, предотвращающему внешнее вмешательство. Это как лекарство, которое защищают от внешней среды, чтобы избежать его разложения. Точно так же в программировании мы защищаем данные (например, переменные) и код от внешнего вмешательства.
3. Наследование: Проще говоря, наследование позволяет новому классу наследовать свойства и методы существующего класса. Это похоже на то, как ребенок унаследовал определенные черты от своих родителей.
4. Полиморфизм: по-гречески «множество фигур» в ООП относится к способности одной функции или метода работать по-разному в зависимости от входных данных. Подумайте об инструменте, который может выполнять множество задач: от привинчивания к резке.
Изучив эти темы, я узнал о обобщенных классах. Обобщенные шаблоны позволяют нам создавать определения классов, методов или интерфейсов с заполнителем для типа данных. Другими словами, дженерики позволяют вам создать класс или метод, который может обрабатывать любую форму данных. Вместо привязки к определенному типу данных (например, «int» или «string») вы используете общий заполнитель, часто обозначаемый как ‹T›. Это помогает написать метод или класс один раз и использовать его с несколькими типами данных без необходимости переписывать его для каждого типа.
Одним из наиболее популярных применений дженериков в C# является класс List‹T›, где T представляет любой тип данных.
Общий синтаксис:
Ромбовидные скобки‹ ›. Эти скобки играют решающую роль. Они содержат заполнители, представляющие универсальный тип(ы).
class ClassName<T>
{
// Class members and methods
}
Простой общий пример:
class MyGenericClass<T>
{
private T data;
public void SetData(T value)
{
data = value;
}
public T GetData()
{
return data;
}
}
В этом примере член data имеет тип T, что означает, что он может иметь любой тип данных, указанный при использовании класса.
Первая задача — создание векторного класса:
В течение первой недели задачей было вдохнуть жизнь в частично созданный векторный класс. Реализуйте шесть недостающих функций:Contains, Insert, Remove, RemoveAt, ToString и Clear. Класс был разработан с использованием дженериков, которые, как упоминалось ранее, позволяют нам беспрепятственно работать с любым типом данных.
Функции и мой подход:
- Содержит. Эта функция проверяет, существует ли элемент в нашем векторе. Я использовал простой цикл для перебора вектора и возврата логического значения: true, если элемент найден, и false в противном случае.
- Вставить. Эта функция вставляет элемент в определенную позицию. Сложная часть? Управление позициями других предметов и обеспечение порядка. Сначала я освободил место для нового элемента, сдвинув элементы вправо от указанной позиции и на одно место вправо. Убедившись, что есть место, новый предмет помещали на назначенное место.
- Удалить. Предназначен для удаления определенного элемента из вектора. Если элемент существует, он удаляется, а последующие элементы смещаются, чтобы заполнить пробел. Сначала прошёлся по вектору, чтобы найти целевой элемент. После обнаружения сместите все элементы справа от этого элемента на одно место влево, по сути перезаписав его и отрегулировав размер вектора.
- RemoveAt: небольшое изменение предыдущей функции. Вместо указания элемента вы указываете его положение. Как только предмет удален, все остальное сдвигается вверх, чтобы сохранить непрерывность.
- ToString: функция, возвращающая содержимое вектора в виде строки. Это была простая задача — перебирать элементы и добавлять каждый к строковому формату.
- Очистить. Как следует из названия, он стирает все дочиста, сбрасывая размер вектора на ноль и гарантируя, что не останется никаких элементов.
Тестер-файл:Тестер-файл сопровождал задачу и служил идеальным средством для тестирования и проверки каждой из этих функций.
Размышление: Из всех функций Вставка представляла собой наиболее серьезную проблему, остальные функции были немного проще. Чтобы проверить, что не так с моей реализацией, я использовал метод ToString (который я сделал первым, поскольку он был простым) для печати элементов массива. Затем я проанализировал выходные данные, чтобы найти то, что я понял не так.
Вторая неделя (асимптотические обозначения и сложности алгоритмов):
Фокус сместился с практических задач кодирования на теоретические основы, лежащие в основе нашего кода: алгоритмы и их сложности. Вот что я узнал:
Что такое алгоритм? Алгоритм — это набор шагов для решения конкретной проблемы. Думайте об этом как о рецепте: последовательности инструкций, правильное выполнение которых приводит к желаемому результату.
Анализ алгоритмов. Очень важно понимать, как будет работать алгоритм, особенно по мере роста размера входных данных. Программа, написанная для сортировки списка из 10 элементов, может работать быстро, но что, если список вырастет до 10 000 или миллиона элементов?
Время работы.Одним из ключевых показателей производительности алгоритма является время его работы, которое характеризует количество выполняемых им базовых операций. Это может варьироваться в зависимости от ввода:
- Лучший случай: минимальное время, необходимое для работы алгоритма.
- Средний случай: среднее время, затраченное на все возможные входные данные.
- Худший случай: максимальное время. Обычно на этом делается акцент, поскольку он обеспечивает верхний предел производительности алгоритма.
Асимптотические обозначения. Для более широкой классификации производительности алгоритмов мы используем асимптотические обозначения. Эти обозначения обеспечивают общее понимание эффективности алгоритма. Три основных обозначения, с которыми вы часто столкнетесь:
- Большой O (O): представляет верхний предел времени работы алгоритма.
- Большая тета (Θ): указывает, что верхний и нижний пределы алгоритма одинаковы.
- Большая Омега (Ом): представляет собой нижний предел времени работы алгоритма.
Зачем использовать большую букву О для обозначения сложности алгоритма:Большинство людей при выборе алгоритма всегда хотят знать, насколько хуже он может стать. Большой — O представляет верхнюю границу алгоритма. Следовательно, это дает наихудшую сложность алгоритма. Big — O хорошо справляется с определением сложности наихудшего случая, что на практике часто более важно, чем сложность среднего и наилучшего случая, описываемая Big Θ.
Задания:
Первой задачей был подсчет операций наихудших случаев для данных алгоритмов и определение их лучшей, средней и самой медленной скорости с использованием нотации Big-𝛩. Мы также использовали обозначение Big-𝑂, чтобы увидеть, насколько медленно оно может работать в наихудших ситуациях, и Big-𝛺, чтобы увидеть, насколько быстро оно может работать в лучших ситуациях. Это помогло мне понять, как может измениться эффективность алгоритма.
Второй заключался в подсчете операций для заданного набора алгоритмов. Алгоритмы основывались на числах бросков. Позвольте мне рассказать вам о подсчете операций в циклах for.
Для одного цикла, который повторяет все элементы один раз, временная сложность является линейной.
for (int i = 0; i < n; i++) { // Operations count = 1 + (n + 1) + (n)
// Basic operation will run 'n' times
}
Разберем операции:
- Инициализация: int i = 0. Выполняется один раз. Количество операций = 1
- Проверка условия: i ‹ nЭта проверка выполняется для каждой итерации цикла и еще раз, когда цикл завершается. Если цикл выполняется N раз, проверка происходит N+1 раз. Количество операций = N + 1
- Приращение: i++ — это происходит N раз (один раз для каждой успешной итерации). Количество операций = N
- Здесь операция внутри цикла выполняется n раз.
Вложенные циклы
При использовании вложенных циклов, где каждый цикл выполняется n раз, количество операций является квадратичным.
for (int i = 0; i < n; i++) { // Operations count = 1 + (n + 1) + (n)
for (int j = 0; j < n; j++) { // Operations count = n(1 + (n + 1) + (n))
// Basic operation will run 'n^2' times
}
}
Размышления. Ориентироваться в сфере сложности алгоритмов было одновременно увлекательно и сложно. Символы, связанные с асимптотическими обозначениями, поначалу казались загадочным языком. Однако с настойчивостью и практикой они начали обретать смысл. С другой стороны, я обнаружил, что хорошо умею подсчитывать операции, и это стало для меня положительным опытом на этой неделе.
