Одной из самых важных, но иногда сбивающих с толку многих тем в компьютерных науках и разработке программного обеспечения является разработка и анализ алгоритмов. Вы, начинающий программист, который никогда не слышал об этом раньше, возможно, думаете: «Если я решил проблему, я уверен, что моя программа имеет хороший алгоритм / решение»… К сожалению, это не так.

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

Правильность и эффективность алгоритма:

Если вы вошли в эту статью, я предполагаю, что вы знаете основную концепцию термина «алгоритм». То есть алгоритм - это метод / идея / процедура решения проблемы. Это означает: один алгоритм не зависит от среды реализации и ресурсов (языка программирования и оборудования).

Правильность:

Но когда алгоритм работает, можно ли сказать, что алгоритм правильный? Может быть, и нет. Полностью правильный алгоритм - это когда его реализация может решить любой вариант проблемы, предложенной решение, включая неудобные (но возможные) и большие (произвольно большие ) входы (экземпляры проблемы, которые наша программа принимает как параметр / вход).

Поскольку это вводный пост, я не буду больше объяснять правильность алгоритма, но вы можете найти дополнительную информацию об этом по следующим ссылкам и ресурсам:

Книга Стивена Скиены Руководство по разработке алгоритмов;

Как доказать правильность алгоритма Хань Д. ТРАН на Medium.

Эффективность:

Этот термин относится к производительности алгоритма. Алгоритм эффективен, когда он имеет адекватную производительность. Это означает: эффективный алгоритм - это когда он решает проблему, не занимая много времени и не используя большой объем памяти (но помните, что это количество времени, и потребляемая память зависит от типа и масштабности проблемы, которая мы пытаемся решить).

Обозначение Big O и асимптотический анализ:

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

Для более детального изучения общего асимптотического анализа предлагаю вам взглянуть на эту статью об Академии Хана.

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

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

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

А теперь давайте посмотрим на пример:

Предположим, вы кодируете функцию, которая использует обычные инструкции и 2 вложенных цикла, которые зависят от ввода функции (рассмотрим псевдокод):

someFunction(n):
    instruction1;
    instruction2;
    ...
    for(let i = 0; i < n; i++){
        for(let c = 0; c < n; c++){
            instruction;
            result += instruction2;
        }
    }
return result;

В этом коде циклы for заставят внутреннюю инструкцию выполняться n² раз (рассмотрим ввод размера n). Это происходит потому, что n является условием «остановки» в циклах (когда счетчик завершит размер n, увеличивая один за другим на каждой итерации, этот цикл останавливается).

Поэтому правильно сказать, что из-за этих вложенных циклов ваша программа будет иметь сложность O (n²);

Ниже представлена ​​диаграмма нотации Big O:

Если программа выполняется в порядке O (1), это означает, что она имеет постоянное время и никогда не увеличивает время выполнения или количество использованных инструкций.

Если программа выполняется в порядке O (n), это означает, что при вводе размера N временная сложность этой программы будет N. Она напрямую зависит от размера ввода.

Если программа выполняется за O (n²), как в нашем примере выше, это означает, что количество итераций имеет тенденцию повторяться, умноженное на квадрат размера ввода.

…

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

Чтобы узнать больше о нотации Big O, я предлагаю вам взглянуть на следующие ссылки:

Это отличное видео Майкла Самбола на YouTube.

Этот пост Шен Хуан в Free Code Camp By Medium.

Шпаргалка по Big O

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

Почему вам это должно быть небезразлично (и почему иногда возникают проблемы с программированием в целом):

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

Но помните, что использование этих концепций и анализа не гарантирует повышения ваших навыков программирования. От вас зависит научиться и практиковаться в программировании, и помните: кодирование - это сложно. Это нормально - бороться со своим кодом и когда-нибудь (или, часто) расстраиваться, просто сохраняйте хладнокровие и продолжайте учиться, выбирая учиться и кодировать так, чтобы вы чувствовали себя комфортно и довольны им!