Что такое компьютерный алгоритм?

Алгоритм — это список инструкций, которые компьютер может использовать для решения определенной задачи. Алгоритмы используются во всех областях вычислительной техники, и они предназначены для эффективного решения проблем.

Дизайн алгоритма зависит от сложности проблемы, которую он должен решить. Для простых задач может подойти грубая сила. Однако для более сложных задач нужны более сложные алгоритмы.

Компьютерные алгоритмы повсюду

Алгоритмы являются основой всей нашей цифровой жизни. Они помогают нам принимать решения быстрее и эффективнее.

Примеры алгоритмов, которые используются в повседневной жизни, такие как поисковая система Google, система рекомендаций Amazon и система рекомендаций фильмов Netflix, так что алгоритмы повсюду!

Эффективность алгоритма и большой O (n):

Процесс оптимизации также зависит от типа и сложности алгоритма. В некоторых случаях на оптимизацию алгоритма могут уйти дни или недели, а в других — только часы или минуты.

Переменные времени и пространства являются наиболее важными, когда речь идет о большом O (n). Алгоритмы являются важной частью разработки программного обеспечения и вычислительных ресурсов. Одним из компонентов, который имеет решающее значение для их производительности, является большая нотация O (n). Буква O(n) в этой фразе указывает, сколько операций выполняется конкретным алгоритмом, где меньшее число означает более быстрое время выполнения. Также зависит от того, сколько (n) мы говорим. Big O фокусируется на наихудшем сценарии.

Важность операции заключается в ее эффективности в достижении желаемых результатов. Размер операции — это ее зависимость от пространства для получения желаемых результатов.

Чем больше входных данных для вашей операции, тем медленнее она будет выполняться. Существует несколько различных распространенных типов нотации «большой O», которые представляют, как ввод влияет на эффективность операции. К ним относятся O (n), O (1), который является наиболее эффективным алгоритмом, и O (log n) и многое другое…

Как работают алгоритмы?

Алгоритмы используются для сортировки списков инструкций и поиска наилучшего возможного решения или оптимального решения для данной проблемы. Алгоритмы сортировки являются наиболее распространенными алгоритмами, используемыми при обработке данных. Они помогают упорядочивать точки данных, сохраняя их в упорядоченном виде, чтобы к ним можно было легко получить доступ.

Список различных методов алгоритмов сортировки не будет полным без упоминания линейной сортировки, которая на самом деле является не алгоритмом, а методом, который можно использовать с любым другим методом сортировки.

Можно разделить на простые и сложные:

  • Простые алгоритмы сортировки называются «пузырьковой сортировкой» и «сортировкой вставками».
  • Сложные алгоритмы сортировки включают «быструю сортировку», «сортировку слиянием» и «сортировку кучи».

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

Алгоритм можно измерить двумя способами:

Временная сложность алгоритмов

Временная сложность — это верхняя граница времени выполнения алгоритма. Он выражается через функцию, асимптотическую запись и постоянное значение. Это может быть записано в виде уравнения, графика или таблицы, чтобы показать зависимость функции от независимой переменной. Временная сложность O(n) означает, что алгоритм завершится за серию логических шагов, соответствующих числу n.

Пространственная сложность алгоритмов

Объемная сложность — это мера того, сколько места требуется для выполнения алгоритма. Пространственная сложность алгоритмов может быть измерена несколькими способами, в том числе: количеством итераций, количеством битов, обработанных каждой операцией, или количеством слов, обработанных за каждую итерацию. Алгоритм O(n) является линейным по размеру входных данных. Это означает, что требуется время, коррелированное с размером входных данных, вплоть до некоторого максимального объема работы.

Несколько методов решения проблемы?

Существует множество подходов к решению проблемы, которые можно классифицировать по разным критериям. Обратите внимание, что это всего лишь мое мнение для классификации типа проблемы, которую я пытаюсь решить.

Наиболее распространенные типы:

  1. Разделяй и властвуй: умный способ решить проблему. Во-первых, разделите проблему на более мелкие подзадачи, решите эти более мелкие проблемы и объедините все решения в окончательное решение проблемы.
  2. Грубая сила: подразумевают перебор всех возможных решений, пока не будет найдено удовлетворительное решение.
  3. Рандомизировано: использовать случайное число во время вычисления, чтобы найти решение проблемы.
  4. Жадный: поиск эффективного решения для меньшей части, а затем распространение этого оптимального решения на остальные части
  5. Рекурсивный: используются для решения более крупных и сложных версий проблемы путем решения более мелких и простых вариантов.
  6. Возврат: это метод компьютерного программирования, который делит проблему на подзадачи, а затем приводит каждую к попытке решения. Если желаемое решение не будет достигнуто, он будет работать в обратном направлении, находя путь, который продвигает его вперед в проблеме.
  7. Динамическое программирование: фокусируется на решении сложных проблем в серии более простых задач, которые решаются только один раз, а не на повторном вычислении для каждой отдельной проблемы. По крайней мере, вычислив его за один раз, вам нужно где-то сохранить его, чтобы вызывать его при необходимости.
  8. Обход указателя или поиск пути: при поиске на графике или в сети важно использовать проверенный алгоритм поиска. Обход указателя — это тип алгоритма поиска, который можно использовать для поиска кратчайшего пути от одного узла графа к другому. Например, если мы хотим найти кратчайший маршрут от узла 1 к узлу 2, используя обход указателя, мы должны начать с поиска ближайшего соседа узла 1, а затем, если его нет, искать ближайшего соседа родительского узла.
  9. Хеш-таблица: Алгоритмы хеш-таблиц используются для различных целей, таких как обнаружение столкновений и поиск пути. Обнаружение столкновений — это когда вы хотите убедиться, что два объекта не пересекаются друг с другом, а поиск пути — это процесс вычисления кратчайшего расстояния между двумя или более точками.

У нас проблемы

Как решить на простом английском?

Первое, что нужно сделать, это прочитать задачу и убедиться, что вы понимаете, что инструкции просят вас сделать.

Затем определите возможные значения для всех переменных, указанных в задаче, и попытайтесь найти логическое решение для каждой переменной.

Наконец, попробуйте написать алгоритм, начните со слов, а не с кода, напишите то, что знает каждый программист, это называется «псевдокод».

Что такое псевдокод?

Когда мы думаем о программировании, часто можно увидеть псевдокод. Это описательные слова на вашем языке, используемые программистами для разработки алгоритма или функций другой системы.

Этот язык программирования может использовать структурные соглашения обычных языков, но он предназначен для чтения человеком, а не для машинного чтения.

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

Вот пример того, как мы думаем, когда сталкиваемся с проблемой, и как мы ее решаем.

Конечно, это всего лишь мое мнение, но я надеюсь, что вы смогли что-то из него почерпнуть. Я получу эту проблему от буквенный код

Эта задача об анаграммах. Анаграмма — это слово, созданное путем перестановки букв другого слова. Новое слово всегда будет содержать все исходные буквы исходного слова, но не в той же последовательности.

Пример 1

Вход: строки = [«eat»,»tea»,»tan»,»ate»,»nat»,»bat»]

Выход: [[«bat»],[«nat»,»tan»],[«ate»,»eat»,»tea»]]

Вы прочитали описание, увидели пример и провели исследование в Google. Все это должно заранее подготовить вас к тому, что запрашивается и что включать в ваши строки кода.

Конечно, вы все еще пытаетесь понять, как поместить это в код, но теперь, когда у вас есть понимание решения, вы можете над ним работать.

Мои мысли пошаговая процедура будет выглядеть следующим образом:

1. Я мог получить по одному экземпляру каждого слова из входных данных.

2. Этот экземпляр следует сделать экземпляром по умолчанию, и его следует отсортировать.

3. Опять же, этот экземпляр по умолчанию будет значением ключа, с которым собираются другие экземпляры.

4. Эта коллекция представляет собой массив, в котором эти значения получены из отсортированного значения ключа.

5. Если я не смог найти несколько экземпляров, я просто верну любой полученный экземпляр.

Теперь давайте разберем его еще дальше, представив, что мы пишем несколько строк кода. Но этот код будет псевдокодом.

Итак, нам нужна некая таблица, которая может хранить пару ключ-значение. Ключ будет отсортированным экземпляром слова по умолчанию, а значения будут массивом этих нескольких значений экземпляра в пределах одних и тех же символов одного и того же слова. Если мы не смогли найти других вхождений того же слова, мы поместили его в один массив.

Так,

цикл по входному массиву

отсортируйте каждую строку, чтобы сделать ее ключом по умолчанию, о котором мы говорили выше

Существует ли ключ в хеш-таблице, а затем поместите несортированную версию в его значения.

Если нет, то создайте массив с текущим значением в цикле

Исходный код в Javascript:

function groupAnagrams(strs) {

//creating the Hash Table

const hashTable = {}

  for (let i = 0; i < strs.length; i++){ //Loop through the input list
  
  // Creating the default key by sorting out the value from each string
  
  // To use the Sort method in JS, you need to use it on an array.
  
  // By using the Split() method, you create an array from this current value that you standing on.
  
  // By using the join() method, you recreate the string from the group of characters you created with the split() method above.
  
    const defKey = strs[i].split('').sort().join('')
  
    if (hashTable[defKey]){ 

  //Checking if the hash table has this value if yes, push the current value which is in that case going to be  different instance from the sorted default instance.
  
    hashTable[defKey].push(strs[i])
  
    } else {
  
    // if not just initialize it with an array
  
    hashTable[defKey] = [strs[i]]
  
    }
  
  }

//Another great method in JS to help you flat all arrays created in the values of hash Table into one array

return Object.values(hashTable)

};

Исходный код на Python:

def groupAnagrams(strs):
  hashTable = {}
  for s in strs:
    defKey = ''.join(sorted(s))
    if defKey in hashTable:
      hashTable[defKey].append(s)
    else:
      hashTable[defKey] = [s]

  return hashTable.values()