(Введение в алгоритмы) Сложность времени и пространства, понятная каждому

внешний интерфейс алгоритм
(Введение в алгоритмы) Сложность времени и пространства, понятная каждому

Как вы понимаете алгоритмы?

Проще говоря, та же функция

  • Код, написанный другими, занимает 100 МБ памяти и выполняется за 100 миллисекунд.
  • Код, который вы написали, занимает 500 МБ памяти для запуска, занимает 1000 миллисекунд или даже больше.

так

  1. Есть два очень важных критерия для измерения качества кода:运行时间а также占用空间, о чем мы поговорим позжевременная сложностьа такжекосмическая сложность,也是学好算法的重要基石
  2. В этом же и разница между осадным львом, знающим алгоритмы, и теми, кто этого не умеет, и, что более важно, разница в зарплате, потому что на собеседованиях на хорошо оплачиваемых крупных фабриках в основном есть алгоритмы

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

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

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

посмотреть на каштаны

function foo1(){
    console.log("我吃了一颗糖")
    console.log("我又吃了一颗糖")
    return "再吃一颗糖"
}

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

Так что насчет каштана внизу?

function foo2(n){
    for( let i = 0; i < n; i++){
        console.log("我吃了一颗糖")
    }
    return "一颗糖"
}

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

let = 0               ：执行 1 次
i < n                 : 执行 n+1 次
i++                   : 执行 n+1 次
console.log("执行了")  : 执行 n 次
return 1              : 执行 1 次

Общее количество выполнений этой функции равно 3n + 4 раза, верно?

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

T(n) = O( f(n) )

n 是输入数据的大小或者输入数据的数量  
T(n) 表示一段代码的总执行时间   
f(n) 表示一段代码的总执行次数   
O  表示代码的执行时间 T(n) 和 执行次数f(n) 成正比

Полная формула выглядит очень хлопотно, не волнуйтесь,Просто знай эту формулу, просто чтобы вы знали, что мы подразумеваем под сложностью алгоритмаO()Как приходите, мы обычно указываем, что сложность алгоритма в основном используется.O()Читайте в больших евклидовых обозначении, это письмо не ноль

использовать только одинO()сказал, что, казалось бы, сразу легче понять

Возвращаясь только что к двум примерам, две приведенные выше функции

  • Первая функция выполняется 3 раза, что составляет O(3) с точки зрения сложности.
  • Вторая функция выполняется 3n + 4 раза, сложность O(3n+4)

Как вы думаете, это все еще очень проблематично, потому что, если логика функции одинакова, но количество выполнений разное в несколько раз, например, O (3) и O (4), в чем разница? Писать два вида немного избыточно, поэтому по сложности есть единое упрощенное представление, и эта упрощенная оценка времени выполнения — наша окончательная时间复杂度

Упрощенный процесс выглядит следующим образом

  • Если только константа непосредственно оценивается как 1, временная сложность O (3) равнаO(1), не говоря уже о том, что он выполняется только один раз, но представление временной сложности постоянного уровня. В нормальных условиях, пока в алгоритме нет циклов и рекурсии, даже при наличии десятков тысяч строк кода временная сложность составляет O(1).
  • В O(3n+4) константа 4 почти не влияет на общее количество выполнений, которым можно пренебречь напрямую, а коэффициент 3 мало влияет, потому что и 3n, и n одного порядка, поэтому константа 3 как коэффициент также оценивается как 1 или может пониматься какудалить коэффициент, поэтому временная сложность O(3n+4) равнаO(n)
  • Если это многочлен, необходимо сохранить только самый высокий порядок n.,O( 666n³ + 666n² + n ), член высшего порядка в этой сложности равен n в третьей степени. Поскольку с увеличением n рост следующих элементов намного меньше, чем элемент самого высокого порядка n, поэтому элементы ниже этого элемента напрямую игнорируются, а также игнорируются константы.时间复杂度为 O(n³)

Если вы не понимаете здесь, сделайте паузу, чтобы понять

Затем объедините каштаны, чтобы увидеть общую временную сложность

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

O(1)

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

function foo(){
    let n = 1
    let b = n * 100
    if(b === 100){
        console.log("开始吃糖")
    }
    console.log("我吃了1颗糖")
    console.log("我吃了2颗糖")
    ......
    console.log("我吃了10000颗糖")
}

O(n)

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

function foo1(n){
    for( let i = 0; i < n; i++){
        console.log("我吃了一颗糖")
    }
}
function foo2(n){
    while( --n > 0){
        console.log("我吃了一颗糖")
    }
}
function foo3(n){
    console.log("我吃了一颗糖")
    --n > 0 && foo3(n)
}

O(n²)

Например, вложенные циклы, как показано ниже, внутренний цикл выполняется n раз, внешний цикл также выполняется n раз, общее время выполнения равно n x n, а временная сложность равна квадрату n, что равноO(n²). Предположим, что n равно 10, тогда внутри будет напечатано 10 x 10 = 100 раз.

function foo1(n){
    for( let i = 0; i < n; i++){
        for( let j = 0; j < n; j++){
            console.log("我吃了一颗糖")
        }
    }
}

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

function foo2(n){
    for( let k = 0; k < n; k++){
        console.log("我吃了一颗糖")
    }
    for( let i = 0; i < n; i++){
        for( let j = 0; j < n; j++){
            console.log("我吃了一颗糖")
        }
    }
}

//或者下面这样，以运行时间最长的，作为时间复杂度的依据，所以下面的时间复杂度就是 O(n²)
function foo3(n){
    if( n > 100){
        for( let k = 0; k < n; k++){
            console.log("我吃了一颗糖")
        }
    }else{
        for( let i = 0; i < n; i++){
            for( let j = 0; j < n; j++){
                console.log("我吃了一颗糖")
            }
        }
    }
}

O(logn)

Возьми каштан, вот пакет сахара

asdf.jpeg

В этой пачке 16 конфет. Му Хуа съедает половину этой пачки конфет каждый день. Сколько времени нужно, чтобы их съесть?

Значит, 16 постоянно делится на 2, а после деления несколько раз получается 1? выразить в коде

function foo1(n){
    let day = 0
    while(n > 1){
        n = n/2
        day++
    }
    return day
}
console.log( foo1(16) ) // 4

Влияние количества циклов в основном исходит от n/2, и на этот раз сложностьO(logn), откуда такая сложность, не волнуйтесь, продолжайте читать

Другой пример следующий

function foo2(n){
    for(let i = 0; i < n; i *= 2){
        console.log("一天")
    }
}
foo2( 16 )

Печать внутри выполняется 4 раза, основное влияние количества циклов исходит от i *= 2 , на этот раз сложность такжеO(logn)

Откуда взялся этот O(logn), вот еще одинматематика в третьем классеТочка знаний, логарифм, давайте посмотрим на картинку

未标题-1.jpg

Если вы этого не понимаете, прочтите еще раз и поймите правила

  • 真数: Это настоящее число, в данном вопросе это 16.
  • 底数: это закон изменения стоимости Например, каждый цикл i*=2, и это умножение на 2 является законом. Например, если значение равно 1,2,3,4,5..., основание равно 1, а закон изменения каждого числа равен +1.
  • 对数: В этом вопросе можно понять, сколько раз х2 умножается, это количество раз

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

ab= n   читается как основание a, логарифм b = n, в этом вопросе мы знаем значения a и n, что равно   2b= 16, затем найдите b

Преобразуйте эту формулу в следующий вид

logan = b    в этом вопросе равно   log216 = ?   Ответ 4

Формула фиксирована, это 16 не фиксировано, это n, которое мы передали, поэтому можно понять, что эта проблема состоит в том, чтобы найти журнал2n = ?

С точки зрения временной сложности это O(log2n), поскольку временная сложность требует удаления констант и коэффициентов, а основание лога совпадает с коэффициентом, его также необходимо удалить, поэтому окончательная правильная временная сложность равнаO(logn)

emmmmm.....

Если вы не понимаете, вы можете сделать паузу, чтобы понять

Другие имеют некоторую временную сложность, яот быстрого к медленномуРасполагаются в следующем порядке

сложность имя
O(1) постоянная сложность
O(logn) логарифмическая сложность
O(n) Линейная временная сложность
O(nlogn) Линейно-логарифмическая сложность
O(n²) квадратный
O(n³) куб
O(2n) Индекс, небольшой объем данных не подойдет
O(n!) факториал, еще медленнее

В чем разница между этими временными сложностями?Посмотрите на картинку

未标题-3.jpg

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

В общем, временная сложность — это тенденция роста времени выполнения, тогда пространственная сложность — это тенденция роста объема памяти.

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

Пространственная сложность — это то, сколько памяти требуется алгоритму и сколько места он занимает.

Обычно используемая пространственная сложностьO(1),O(n),O(n²)

O(1)

Пока нет дополнительного прироста пространства из-за выполнения алгоритма, даже если это 10 000 строк, сложность пространства одинакова.O(1), такие как следующие, временная сложность также O (1)

function foo(){
    let n = 1
    let b = n * 100
    if(b === 100){
        console.log("开始吃糖")
    }
    console.log("我吃了1颗糖")
    console.log("我吃了2颗糖")
    ......
    console.log("我吃了10000颗糖")
}

O(n)

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

function foo(n){
    let arr = []
    for( let i = 1; i < n; i++ ) {
        arr[i] = i
    }
}

O(n²)

O (n²) Эта пространственная сложность обычно возникает в случае двумерных массивов или матриц.

Излишне говорить, что вы определенно понимаете, что происходит

Нужно пройти, чтобы сгенерировать такой формат

let arr = [
    [1,2,3,4,5],
    [1,2,3,4,5],
    [1,2,3,4,5]
]

Эпилог

Я надеюсь, что эта статья может вам немного помочь, кроме того, попросите лайк, спасибо! ^_^

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

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

Категории