Временная сложность алгоритма и пространственная сложность

алгоритм
Временная сложность алгоритма и пространственная сложность

Это 16-й день, когда я участвую в Gengwen Challenge, проверьте подробности мероприятия:Обновить вызов

Преамбула

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

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

Основная информация

Классификация содержание
Частота обновления ежедневно (по возможности)
язык python /java
Область применения интервью

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

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

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

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

no_free_lunch.jpeg

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

programming_language.jpeg

язык

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

  • javascript
  • java
  • python
  • go
  • rust
  • cpp

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

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

Так появился другой, более общий подход: **Большая нотация O**, т.е. T(n) = O(f(n))

const n = 10;
var j = 0;
for(let i=1; i<=n; ++i)
{
   j = i;
   j++;
}

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

шкала сложности

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

  • Постоянный порядок O(1)
  • Логарифмический O(logN)
  • Линейный порядок O (n)
  • Линейный логарифмический порядок O(nlogN)
  • Квадратный порядок O (n²)
  • Кубический порядок O (n³)
  • Порядок степени K O (n ^ k)
  • Экспоненциальный порядок (2^n)
const N = 10;
var a = 0;
var b = 0;
for (let i = 0; i < N; i++) {
    a = a + Math.random()    // $N \times 1$ 操作 = O(N)
}
измерение ценность
временная сложность O(N)
космическая сложность O(1) 
for (let i = 0; i < N; i++) {
    a = a + Math.random()    // $N \times 1$ 操作 = O(N)
    b = b + Math.random()    // $N \times 1$ 操作 = O(N)
}
измерение ценность
временная сложность O(N) + O(N) = O(N)
космическая сложность O(1) 
for (let i = 0; i < N/2; i++) {
    b = b + Math.random()    // $ \frac{1}{2} N \times 1$ 操作 = O(N)
}
измерение ценность
временная сложность 12×O(N)=O(N) \frac{1}{2} \times O(N) = O(N)
космическая сложность O(1)

Пространственная сложность равна O(1), потому что она не зависит от N, так что это постоянная сложность.

for (let i = 0; i < N; i++) {
    for (let j = N; j > i; j--) {
        a = a + i + j;
    }
}

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

 i = 0: j = N...1 (N)
 i = 1: j = N...2 (N-1)
 i = 3: j = N...3 (N-2)
 i = N-1: j = N (1)

временная сложность, потому чтоO(N2)O(N^2)Сложность строго больше, чемO(N)O(N)сложность1+2+3,⋯+N=N×N+12=N×N2+N2 1 + 2 + 3 ,\dots + N = N \times \frac{N + 1}{2} = N \times \frac{N}{2} + \frac{N}{2} =12×O(N2)+12×O(N)=O((N2)+O(N)=O((N2)= \frac{1}{2} \times O(N^2) + \frac{1}{2} \times O(N) = O((N^2) + O(N) = O((N^2)

измерение ценность
временная сложность O(N2)O(N^2)
космическая сложность O(1)O(1)
```
var a = 0;
var i = N;

в то время как (я > 0) { а += i;//1 операция я /= 2;//1 операция }

在算法中，**时间复杂度**度是一个单位，而不是具体用的时间，这一点希望大家一定要清楚，我们通过不同量级(单位)来衡量单位。例如我们平时使用时间单位，时、分和秒，而不是具体用了几个小时。
 而不是具体给出某一个算法具体耗时。这一点对于初学者可能是比较confusing
###  常数阶 $O(1)$ 

```python
console.log("hello world")

Операция, выполненная здесь,O(1)O(1)Постоянная операция, выдающая HelloWorld только три раза, считаетсяO(1)O(1)Здесь 1 означает постоянную единицу, а не значение конкретного числа 1.

Линейный порядокO(n)O(n) 

var N = 10;

for(let i = 0; i < N; i++){
    console.log("hello world");
}

Здесь есть цикл, который говорит, что выполнение операции вывода helloWord связано с N, поэтому запишите его какO(N)O(N)

Квадратный порядокO(n2)O(n^2) 

for(let i =0; i < N; i++){
    for(let j=0; j< N; j++){
        console.log(i)
    }
}

кубический порядокO(n3)O(n^3) 

for(let i =0; i < N; i++){
    for(let n=0; n< N; n++){
        for(let m =0; m < N; m++){
            console.log(i)
        }
    }
}

T(n)=n*n*n=n3T(n) = n * n * n = n^3Теперь нетрудно обнаружить, что слоев цикла for несколько, а временная сложность в несколько раз больше n.

логарифмическийO(log⁡n)O(\log n) 

var N = 32
while(N > 0){
  console.log("hello world")
  N = N/2
}

Вот одна вещь, которую мы хотим сказать, а именно этоO(log⁡n)O(\log n)намного меньше, чемO(n)O(n)пока мы помнимO(1)<O(1) <

O(nlog⁡n)Линейный логарифмический порядокO (n \ log n) линейный логарифмический порядок

var N = 100
for(let i=1; i<N; i++)
{
    i = 1;
    while(i<N)
    {
        i = i * 2;
    }
}

T(n)=n*log⁡nT(n) = n * \log n

Категории