В 2019 году, в этот необычный год, Китай и Соединенные Штаты贸易战, различные крупные заводы裁员. В результате текущий интернет-рынок не очень хорош, и ситуация очень мрачная. Некоторые люди говорят, что этот год был худшим годом для Интернета за последнее десятилетие и, возможно, лучшим годом следующего десятилетия. Что нам делать в таком неспокойном мире? Я также слышал от многих друзей, что собеседования в этом году относительно строгие, характеризующиеся"要求高、薪资低". Я также часто слышу, как они говорят, что некая крупная фабрика взяла тест на алгоритм рукописного ввода, и он тут же провалился. Как программисты, в такой сложной отраслевой ситуации и сильном конкурентном давлении мы можем только постоянно улучшать свои собственные возможности, чтобы гарантировать, что существует立足之地.
Курс «Структуры данных и алгоритмы» остановил меня в студенческие годы. Услышанное имя кажется неясным и требует больших математических знаний, чтобы предсказать. Я считаю, что многие люди такие же, как я, когда я учился в школе, я мало что знал об этом, а когда я пришел на работу, я редко использовал его, и он исчез. Но это становится для вас препятствием для интервью и поиска хорошей платформы. Многие крупные заводы очень заинтересованы в программистах基本功, так на собеседовании алгоритм запрограммировал общие вопросы теста, почему? Поскольку базовые знания подобны фундаменту здания, они могут определить вашу технологию.高度и深度. Поэтому общие производители смотрят, есть ли у вас потенциал для развития этой технологии.("所以大家要夯实基本功了。")
На мой взгляд, есть три базовых знания, которые должны усвоить бэкенд-программисты."数据结构与算法","计算机系统","操作系统Linux". В эту эпоху, когда всем приходится рвать алгоритм руками, я не могу спать всю ночь(纯属扯淡) решил привести всех к совместному изучению трех базовых знаний.Открывающая серия этой серии - «Структуры данных и алгоритмы разрыва рук».После завершения каждой серии будет открыта следующая серия, так что не волнуйтесь.
Сначала поставьте картинку, чтобы все могли понять, о чем пойдет речь в этой серии.
Если вам интересна эта моя серия, вы можете обратить внимание на мой официальный аккаунт и провести вас по «сверхъестественной дороге», получить высокооплачиваемое предложение, стать техническим экспертом, стать большим заводом и выйти замуж.Белая, богатая и красивая девушка, Идя к пику жизни, я чувствую себя немного взволнованным, когда думаю об этом. (пожалуйста, позвольте мне взорвать 🐂)
Сюда, сюда, сюда, сюда, сюда с QR-кодом! ! !
Добро пожаловать, чтобы отсканировать код, чтобы следовать! ! !
2. Проверка математических знаний
Прежде чем мы систематически изучим структуры данных и алгоритмы, давайте вкратце повторим некоторые математические знания, которые, я думаю, почти все забыли, вернули ли они их учителю после того, как закончили обучение? Спешите, приходите и просмотрите со мной.
2.1 Индекс
Показатель степени — это параметр в операции возведения в степень aⁿ (a≠0), a — основание, n — показатель степени, причем показатель степени расположен в правом верхнем углу основания, а операция возведения в степень означает умножение показателей степени и оснований. Когда n является положительным целым числом,ⁿПредставляет n умножений a. Когда n=0, аⁿ=1. «Энциклопедия Байду»
指数：就是aⁿ中的n。
底数：就是aⁿ的a
幂运算：指数个底数相乘。
Формула мощности:
2.2 Логарифмы
Если а в степени х равно N (а > 0, а а не равно 1), то число х называется логарифмом числа N по основанию а (логарифмом), обозначаемым как. где а называется логарифмическимбаза, N называетсяистинное число. «Энциклопедия Байду»
在计算机科学中，除非有特别的声明，否则所有的对数都是以2为底的。
формула:
Просто перечислите две формулы, каждый может посмотреть на них, узнать, что это такое对数.
3. Временная сложность
для алгоритма时间复杂度, могут подумать некоторые друзья, а не просто ли оценить время выполнения куска кода, мы можем сделать мониторинг, просто посмотреть на потребление времени каждым интерфейсом, почему это так хлопотно, но и проанализировать время сложности Потрать. Но этот мониторинг — операция постфактум, только код运行时, чтобы узнать код, который вы написали效率Высокая или нет, но как оценить эффективность выполнения куска кода при написании кода?В настоящее время требуется анализ временной сложности. Обычно мы пишем код, который может хорошо сочетать временную сложность и мониторинг.事前,事后анализ, более оптимизированный код.
3.1 Обозначение большого O
Поскольку асимптотическая временная сложность представлена заглавной буквой O, ее также называют大O表示法. Например:O(f(n)).
Общая временная сложность:
Общая временная сложность затраченного времени в порядке от малого к большему:
Способ получения большого O:
3.2 Как анализировать временную сложность
O(1)
int i = 5; /*执行一次*/ int j = 6; /*执行一次*/ int sum = j + i; /*执行一次*/
Текущая функция этого кода должна быть f(n)=3, и она должна быть O(f(n))=O(3), если она используется для большого O, но согласно нашему выводу, первый в большом В нотации Статья используйте 1 для замены константы в функции, поэтому O(3)=>O(1), тогда временная сложность этого кода будет O(1) вместо O(3).
O(logn)
int count = 1; /*执行一次*/ int n = 100; /*执行一次*/ while (count < n) { count = count * 2; /*执行多次*/ }
O(n)
for (int k = 0; k < n; k++) { System.out.println(k); /*执行n次*/ }
Количество выполнений этого кода будет увеличиваться по мере увеличения n, то есть он будет выполняться n раз, поэтому его временная сложность равна O(n).
for (int k = 0; k < n; k++) { for (int l = 0; l < n; l++) { System.out.println(l); /*执行了n*n次/ } }
public int find(int[] arrays, int findValue) { int result = -1; /*执行一次*/ int n = arrays.length; for (int i = 0; i < n; i++) { if (arrays[i] == findValue) { /*执行arrays.length次*/ result = arrays[i]; break; } } return result; /*执行一次*/ }
Давайте проанализируем приведенный выше метод.Функция этого метода состоит в том, чтобы найти значение, которое он хочет, из массива. На самом деле, сложность алгоритма также будет варьироваться в зависимости от фактической реализации.Например, в приведенном выше коде, если длина массива равна 100, число, хранящееся в нем, равно 1-100.
временная сложность в лучшем случае
Если я посмотрю номер 1 в этом массиве, он найдет значение при первом прохождении, а затем выполнитbreakЗавершить текущий цикл, в это время весь код выполняется только один раз, принадлежащий常数阶O(1), что в лучшем случае является временной сложностью этого кода.
временная сложность в худшем случае
Если я ищу число 100 в этом массиве, то массив будет пройден для поиска и возврата, поэтому на этот метод будет влиять размер массива, если размер массива равен n, то чем больше n , исполнение больше раз. принадлежать线性阶O(n), что является наихудшей временной сложностью.
Средняя временная сложность дела
Все мы знаем, что наилучшая и наихудшая временная сложность — это сложность кода в двух крайних случаях, и вероятность возникновения невелика, поэтому введем еще одно понятие“平均时间复杂度”. Мы также рассмотрим этот метод выше, чтобы найти число с n+1 случаями: в позиции массива 0 ~ n-1 и больше не в массиве, поэтому мы накапливаем времена выполнения всех кодов ((1 +2 +3+...+n)+n), а затем разделите на все случаи n(n+1), чтобы получить среднее количество требуемых выполнений.
Процесс получения:
Обозначение Big O, будетОпустить коэффициент, низкий порядок, константа,Таким образом, средняя временная сложность дела равнаO(n).
Однако эта средняя сложность не учитывает вероятность возникновения каждой ситуации, здесь вероятность возникновения n+1 ситуаций различна, поэтому необходимо ввести вероятность возникновения каждой ситуации, а затем проанализировать ее в деталь. findValue находится либо в 1~n, либо не в 1~n, поэтому их вероятности равны, а вероятность данных в каждой позиции в 1 ~ n такая же, как, Согласно закону умножения вероятности, вероятность findValue в любой позиции в 1~n равна, поэтому на основании приведенного выше вывода необходимо добавить вероятность возникновения.
Средняя сложность случая с учетом вероятностей:
Процесс получения:
Это средневзвешенное значение в теории вероятностей, также называемое ожидаемым значением, поэтому полное название средней временной сложности:Средневзвешенная временная сложностьилиОжидаемая временная сложность. Средняя сложность становится, после игнорирования коэффициентов и констант окончательная средневзвешенная временная сложность равна O (n).
4. Пространственная сложность
Объемная сложность алгоритма является мерой размера памяти, временно занятой во время выполнения процесса.Формула расчета объемной сложности алгоритма записывается как:S(n) = O(f(n)), n — размер задачи, а f(n) — функция памяти, занимаемой оператором, относительно n. Так как нотация большой O пространственной сложности и временной сложности одна и та же, мы кратко представим их.
Общие космические сложности от низкой до высокой:
4.1 Как анализировать пространственную сложность
O(1)
public static void intFun(int n) { var intValue = n; //... }
Когда размер памяти алгоритма фиксирован и не имеет прямого отношения к размеру входных данных, сложность памяти записывается как O(1.4 байта).
O(n)
public static void arrayFun(int n) { var array = new int[n]; //... }
Когда пространство, выделенное алгоритмом, представляет собой коллекцию или массив, а его размер пропорционален входному размеру n, сложность пространства записывается как.
public static void matrixFun(int n) { var matrix = new int[n][n]; //... }
Когда пространство, выделенное алгоритмом, представляет собой двумерный массив, а его первое и второе измерения пропорциональны входному размеру n, сложность пространства записывается как.
5. Резюме
за时间и空间Выбор зависит от реальной ситуации в конкретном бизнесе. Иногда нам нужно жертвовать временем ради места, а иногда нам нужно жертвовать пространством ради времени. В эту эпоху стремительного роста производительности компьютерного оборудования, конечно, мы по-прежнему предпочитаем жертвовать пространство в обмен на время.Ведь память еще есть и стоит она не дорого. И это может повысить эффективность и предоставить пользователям лучший опыт.
Что такое временная сложность?
Временная сложность — это мера времени выполнения алгоритма, выраженная в большом O какT(n) = O(f(n)). Общий порядок временной сложности от низшего к высшему:
Что такое космическая сложность?
Сложность пространства — это мера временной памяти, занимаемой алгоритмом во время его работы, и она отмечена большим O какS(n)= O(f(n)). Общий порядок пространственной сложности от низшего к высшему:
6. Ссылка
«Структура данных и анализ алгоритмов»
«Структура данных Dahua»
«Комический алгоритм»
Если вы видите здесь друзей, я считаю, что вы также поддерживаете определенный энтузиазм к обучению. Если вы считаете, что это полезно для вас, пожалуйста, поставьте лайк или посмотрите его для поддержки. Если у вас есть какие-либо вопросы, пожалуйста, оставьте сообщение или подпишитесь мой официальный аккаунт для входа в групповое общение. К тому же в статье есть недоразумения,ошибки в написании,ошибки.Надеюсь все меня поправят.Это самая большая помощь для меня.Спасибо.