«Алгоритмы и структуры данных» Сложность времени и пространства

написать впереди

Некоторые люди могут жаловаться на использование алгоритмов обучения.В лучшем случае их можно использовать при опросе крупных фабрик.Алгоритмы интервью крупных фабрик - это всего лишь ступенька к отсеиванию сильных.Так ли это на самом деле?

Конечно нет.В развитии компьютерной индустрии, будь то front-end или back-end, алгоритмы являются камнем преткновения для продвинутых.Можно сказать, что без алгоритмов вы никогда не станете квалифицированным старшим инженером.Если хотите чтобы попасть на большую фабрику, вам действительно нужно знать алгоритмы, но это не только для собеседований, это тесно связано с нашей программой, некоторые люди говорят, что интерфейсу не нужны алгоритмы? ты поставил знаменитый虚拟DOM (Virtual DOM)где это, это算法与数据结构Некоторые люди могут сказать, что это проявление того, что я не пишу виртуальный DOM. . . Ну а значит всегда хочешь заработать, идешь по техническому маршруту и хочешь получать высокую зарплату, краеугольным камнем является алгоритм

В Интернете есть много алгоритмов и курсов в Интернете, говоря, что вы можете изучить структуры данных алгоритма в течение 7 дней, главных алгоритмов и структур данных в течение 30 дней и т. Д. Не будь глупым, нет ярлыков для алгоритмов, вы можете только Нам полагаться на нас, чтобы накапливать их понемногу. Что вы должны сделать, чтобы полагать, что вы не являетесь гением, а во-вторых - чтобы с каждым днем писать вопросы. Вы можете почистить четыре или пять вопросов в неделю, если вы можете почистить четыре или пять вопросов в неделю короткие вовремя. После периода не касаться алгоритма, он все еще будет забыт, поэтому важно продолжить

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

что такое структура данных

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

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

Например, цифра 1 или символA, которая является структурой данных

например свидание2020年12月14日, который состоит из трех форматов года, месяца и дня, а также является структурой данных

Например, массив[1, 'a', '2020年12月14日'], который представляет собой комбинацию чисел, символов и форматов даты, а также структуру данных

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

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

что такое алгоритм

Что такое алгоритм, мы все знаем1+2+3=6, почему оно равно 6, можно сказать, 1 плюс 2 равно 3, а два 3 плюс равно 6, это математический здравый смысл, который знают младшие школьники, это алгоритм в широком смысле

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

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

Алгоритм постановки задачи — это процесс перехода от абстракции к конкретности.

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

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

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

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

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

Прежде чем говорить о временной сложности, мы должны сначала понять понятие количества выполнений кода, которое также можно назвать частотой операторов или временной частотой.T(n)выражать

Давайте используем пример, чтобы объяснить шаг за шагом, сначала давайте посмотрим на функциюfn1

function fn1(){
  console.log("句末")
  console.log("isboyjc")
}

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

Очевидно, внутри этой функции есть только два утверждения, а именноconsole.log("句末")а такжеconsole.log("isboyjc"), то мы говорим, что количество исполнений кода в теле функции равно 2

Давайте еще раз посмотрим на функциюfn2

function fn2(n){
  for(let i = 0; i < n; i++){
    console.log("句末")
  }
}

Сначала рассмотрим функциюfn2Есть несколько исполняемых операторов

let i = 0
i < n
i++
console.log("句末")

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

let i = 0Этот оператор объявления используется только в первый разforВыполнить один раз при объявлении цикла

i < nКоличество выполнений этого оператора зависит от размера формального параметра n,n = 3когда, то естьi=0,i=1,i=2,i=3будет выполняться, то есть количество раз выполнения этого оператора равноn + 1второсортный

i++Количество выполнений этого оператора также зависит от размера формального параметра n.n = 3когда, то естьi=0,i=1,i=2будет выполнено, когда n раз

console.log("句末")Количество выполнений этого оператора по-прежнему зависит от размера формального параметра n.n = 3будет выполнено 3 раза, то этот оператор будет выполнен n раз внутри функции

1 + (n + 1) + n + n = (3n + 2)

тогда функцияfn2Внутреннее исполнение3n + 2второсортный

Общее количество выполнений фрагмента кода, который мы обычно используемT(n)чтобы указать, затем вызовите выше один разfn1/fn2Общее количество выполнений двух функций равно

T(n) = 2	// fn1
T(n) = 3n + 2 	// fn2

Вышеупомянутое n относится к масштабу проблемы, то есть к размеру или количеству входных данных, вы также можете просто понимать это какTсама функция,nэто параметр, то есть

функцияfn1В любом случае количество исполнений равно 2

функцияfn2Общее количество выполнений будет варьироваться в зависимости от размера n

Давайте подумаем, можем ли мы использовать общее количество выполнений фрагмента кода для измерения скорости выполнения?

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

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

После уточнения этой концепции мы можем рассчитать временную сложность или использовать приведенное вышеfn1/fn2Пример двух функций

// fn1
T(n) = 2

// fn2
T(n) = 3n + 2

Сначала рассмотрим функциюfn1, его общее количество исполнений равно 2, a常数(常数级), то есть общее количество выполнений этой функции равно 2 всякий раз, когда это постоянное значение, тогда мы используем временную сложностьOДля ее представления ее можно непосредственно оценить как 1, то есть временная сложность равнаO(1)

Давайте еще раз посмотрим на функциюfn2, время его выполненияT(n)да3n + 2который常数*n + 常数, здесь мы можем видеть, что常数*nа также+常数Две части, при увеличении n будет изменяться только первая часть, а вторая часть останется неизменной, поэтому последними постоянными константами можно пренебречь при выражении временной сложности, т.е.常数*n,а также常数*nМы также можем напрямую рассматривать константу как 1 или игнорировать эту константу как коэффициент, тогда мы, наконец, можем получить функциюfn2Временная сложность равна n, то естьO(n)

PS: я знаю, что кто-то, возможно, вернул учителю математические знания, поэтому объясните

постоянный:Константа относится к обычному значению, которое можно просто понимать как фиксированное значение.

коэффициент:Коэффициенты относятся к числовым факторам в мономе алгебраического выражения, например.a = 1 * a, то его коэффициент равен 1,2b = 2 * b, то его коэффициент равен 2

Давайте возьмем другой пример, так как следующий полином относится к функцииT(n), найти его временную сложность

T(n) = 10n^4 + 100n^2 + 1000

На самом деле, для полиномов нам нужно только сохранить член высшего порядка, то есть сохранить число высшего порядка п. В этом примере зарезервирована 4-я степень п. Коэффициенты и константы можно игнорировать , Окончательная временная сложностьO(n^4)

В заключение:

T(n)Когда постоянна, временная сложность равнаO(1), а временная сложностьO(保留T(n)的最高次项并去掉最高次项的系数)

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

пример 1:

function fn01(){
  console.log("你看这是啥")
  console.log("这是一个输出")
  console.log("哈哈哈")
  let a = 1
  return a
}

вышеуказанная функцияfn01В нем всего одна фразаO(1), что является постоянной временной сложностью

Пример 2:

function fn02(n){
  for(let i = 0; i < n; i++){
    console.log("这是一个输出🎓")
  }
}

Как и выше, функцияfn02То же, что и вышеприведенный примерfn2, петля, временная сложностьO(n), что является линейной временной сложностью

Пример 3:

function fn03(n){
  for(let i = 0; i < n; i++){
    console.log("外层循环")
    for(let j = 0; j < n; j++){
      console.log("内层循环")
    }
  }
}

Этот вопрос отличается от приведенного выше.Давайте сначала рассмотрим только внутренний цикл.Внутренний цикл, вероятно, будет выполнен n раз, затем посмотрим на внешний цикл, который будет выполнен n раз, и, наконец,n * n = n^2, функцияfn03Сложность времениO(n^2), это временная сложность квадратного уровня, если это трехслойная петля, временная сложность равнаO(n^3), кубическая временная сложность

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

Пример 4:

Давайте посмотрим на следующую функциюfn04

function fn04(n){
  for(let i = 0; i < n; i++){
    console.log("外层循环")
    for(let j = 0; j < n; j++){
      console.log("内层循环")
    }
  }
  
  for(let i = 0; i < n; i++){
    console.log("哈哈哈")
  }
}

В этой функции есть двойной цикл, а есть одинарный цикл, то есть количество выполнений примерно равноn^2 + n, согласно тому, что мы сказали выше, чтобы сохранить член высшего порядка, то функцияfn04Временная сложностьO(n^2)

Пример 5:

Алгоритм определенно не просто обычный цикл выше, давайте посмотрим на следующий.

function fn05(n){
  for(let i = 0; i < n; i++){
    console.log("外层循环")
    for(let j = i; j < n; j++){
      console.log("内层循环")
    }
  }
}

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

когдаi = 0, внутренний цикл будет выполнен n раз

когдаi = 1, внутренний цикл выполнится n - 1 раз

когдаi = 2, внутренний цикл выполнится n - 2 раза

когдаi = 3, внутренний цикл выполнится n - 3 раза

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

когдаi = n - 2, внутренний цикл будет выполнен дважды

когдаi = n - 1, внутренний цикл будет выполнен один раз

Наконец, мы суммируем время выполнения n внутренних циклов, чтобы получить окончательное неточное общее время выполнения.

T(n) = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1

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

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

Например:1,3,5,7,9……（2n-1)Арифметическая последовательностьS(n)Общая формула термина:S(n) = S1 + (n-1) * d, первые n членов и формула следующие

S(n) = n*S1 + n*(n - 1)*d/2

// 或

S(n) = n*(S1 + Sn)/2

Таким образом, мы можем вычислить результат.В приведенной выше последовательности допуск d равен -1, и мы можем внести его в формулу.Вторая формула простая, а вторая лучше.Результаты расчета такие же .

// n*(S1 + Sn)/2

n*(n + 1)/2 = (n^2 + n)/2 = (1/2)n^2 + (1/2)n

Наконец мы получили(1/2)n^2 + (1/2)n, и убрать коэффициент по пункту старшего порядка выше, то есть временная сложность равнаO(n^2)

Пример 6:

Давайте посмотрим на другой пример

function fn06(n){
  for(let i = 1; i < n; i *= 2){
    console.log("isboyjc")
  }
}

Всё так же, если не умеете читать, можете попробовать с несколькими параметрами и посмотреть правила

Мы можем использоватьn=2, n=4, n=8, n=16, следите за количеством отпечатков в цикле, конечно, можно и напрямую запустить код, процесс не слишком большой, давайте посмотрим на результаты напрямую

n=2		时打印1次 T(n)=1
n=4		时打印2次 T(n)=2
n=8		时打印3次 T(n)=3
n=16 		时打印4次 T(n)=4

Основное изображение для количества выполнений - это изображение в операторе цикла.i*=2, каждый раз, когда петля i будет становиться дважды, внимательно наблюдайте, мы можем нарисовать такой обычный результат

n=2		时打印1次 T(n)=1 // 2^1 = 2
n=4		时打印2次 T(n)=2 // 2^2 = 4
n=8		时打印3次 T(n)=3 // 2^3 = 8
n=16 		时打印4次 T(n)=4 // 2^4 = 16

В соответствии с приведенными выше правилами легко найти, что тогда2^执行次数=n,Прямо сейчас2^T(n)=n, мы просимT(n), просто скорректируйте его, то есть логарифм n по основанию 2, то естьT(n)=log_2 n

P.S. Давайте еще раз посчитаем.

логарифм:еслиa^n=b, то есть n-я степень a равна b, и мы находим значение n, то для удобства его можно записать в видеlog_a b, логарифм b по основанию a, где a — основание, b — истинное число, а n — логарифм

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

Промежуточный выводlog_2 nВторосортный,let i = 1будет выполнен только один раз,i<nбудет выполнятьlog_2 n + 1Второсортный,i*=2также будет выполнятьlog_2 nраз, сложив доlog_2 n + log_2 n + 1 + log_2 n,Прямо сейчас3log_2 n + 2, убрав коэффициент 3 и константу 2, получимlog_2 n, при расчете временной сложностиlogБазу также можно опустить, поэтому конечная функцияfn06Временная сложностьO(log n), что является логарифмической временной сложностью

Пример 7:

Наконец, позвольте мне привести вам пример

function fn07(n,m){
  for(let i = 0; i < n; i++){
    while(j < m){
      console.log("你看懂了吗")
      j = j * 2
    }
  }
}

Как показано на рисунке выше, эта функция имеет два параметра, соответствующих внутреннему и внешнему циклам Начнем с внутреннего цикла Знакомо ли это? На самом деле внутренний цикл и вышеприведенная функцияfn06Цикл такой же, только один сfor, б/уwhile, мы не будем описывать временную сложность в предыдущем вопросе, то временная сложность внутреннего цикла равнаO(log n)

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

Два цикла вложены друг в друга, и их можно умножать, поэтому функцияfn07Временная сложностьO(n*log n), что является линейной логарифмической временной сложностью

Как выводит эта функция, вы понимаете?

Кодовые слова слишком утомительны, давайте взглянем на картинку:

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

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

Общие показатели временной сложности:

постоянный уровеньO(1)
логарифмическая шкалаO(log n)
Линейный этапO(n)
Линейная логарифмическая шкалаO(n*log n)
квадратный уровеньO(n^2)
кубический уровеньO(n^3)
К уровень мощностиO(n^k)
экспоненциальныйO(2^n)

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

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

Это конец временной сложности. Мы также перечислим общую временную сложность. Далее давайте посмотрим на пространственную сложность.

космическая сложность

Объемная сложность на самом деле является выражением объема памяти, занимаемого алгоритмом или фрагментом кода во время его выполнения.

О временной сложности мы говорили выше, тогда пространственная сложность будет намного проще

Сложность пространстваS(n), он также будет представлен большой нотацией O, перейдем непосредственно к примеру

пример 1:

function fn001(n){
  for(let i = 0; i < n; i++){
    console.log("空间复杂度")
  }
}

Во-первых, мы знаем, что сложность пространства связана с местом для хранения, а что определяет место для хранения, это должна быть объявленная переменная, давайте перейдем непосредственно к функцииfn001объявления переменных в , только одинi, то есть эта функция только открывает пространство дляiиспользуя, то пространственная сложностьS(n)то естьO(1), Вы могли бы сказатьiНе меняется ли оно все время, да меняется, но как бы оно не менялось, это все равно число, а размер занимаемого места один и тот же

Пространственная сложность такая же, как и временная сложность.Когда переменная, объявленная в коде, является константой и не будет изменяться в соответствии с изменением входящего значения, то ее пространственная сложность равнаO(1)

Пример 2:

function fn002(n){
  let arr = []
  while(n--){
    arr.push(n)
  }
}

В этом примере мы объявляем массив. Мы знаем, что в массиве могут храниться различные типы. В цикле мыnмассив размераarrсерединаpushэлемент, значит,nНасколько большой, массив имеет столько элементов, сколько он занимает столько места, поэтому пространственная сложностьS(n) = O(n)

Резюме космической сложности

В пространственной сложности приведены только два примера, потому что остальные мы, как правило, не используем, а пространственная сложность обычно составляет всего лишьO(1)/O(n)/O(n^2), другие редки, конечно есть, мы знаем временную сложность и затем анализируем пространственную сложность тоже очень хорошо, так что я не буду вдаваться в подробности.

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

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

время против пространства

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

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

Хотя возможно заменить пространство на время, невозможно слепо заменить пространство на время Нам все еще необходимо максимально уменьшить сложность двух измерений В некоторых противоположных случаях можно заменить пространство на время

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

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

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

наконец

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

Рекомендуется чистить вопросы, когда вам скучно на работе.Лучше трогать рыбу и чистить алгоритм, когда вы на работе.В байли нет вреда, и придерживайтесь чистки вопросов каждый день.Давай.

Хранилище алгоритмов GitHub, используйте JavaScript для обновления вопросов по алгоритмам/решения текстовых/видео задач с нуля, приходите и обратите внимание 👉Портал GitHub

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

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