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

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

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

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

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

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

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

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

Переменные времени и пространства являются наиболее важными, когда речь идет о большом O (n). Алгоритмы являются важной частью разработки программного обеспечения и вычислительных ресурсов. Одним из компонентов, который имеет решающее значение для их производительности, является большая нотация O (n). Буква O(n) в этой фразе указывает, сколько операций выполняется конкретным алгоритмом, где меньшее число означает более быстрое время выполнения. Также зависит от того, сколько (n) мы говорим. Big 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. Хеш-таблица. Алгоритмы хэш-таблицы используются для различных целей, например для обнаружения столкновений и поиска путей. Обнаружение столкновений — это когда вы хотите убедиться, что два объекта не пересекаются друг с другом, а поиск пути — это процесс вычисления кратчайшего расстояния между двумя или более точками.

Мы столкнулись с проблемой

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

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

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

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

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

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

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

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

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

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

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

Пример 1

Ввод: strs = ["есть", "чай", "загар", "съел", "натур", "летучая мышь"]

Вывод: [["летучая мышь"],["нат","тан"],["съел","съел","чай"]]

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

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

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

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

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

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

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

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

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

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

So,

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

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

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

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

Исходный код в 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()