Приведите пример константного алгоритма?

Question

[Иван]

Нашёл пример константного алгоритма, но не совсем понимаю, как в данном примере алгоритм не зависит от входных данных

public int GetCount(int[] items) {
    return items.Length;
}

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

Answer 1

[Rsa97]

Оценка сложности алгоритма O() - это то, как меняется время вполнения алгоритма от изменения объёма обрабатываемых этим алгоритмом данных.
O(1) - время не зависит от объёма данных.
O(n) - время растёт пропорционально объёму данных.
O(n²) - время растёт пропорционально квадрату объёма данных.
и т.д.

Получение длины строки может иметь разную сложность в зависимости от языка программирования. Если используется хранение строк с префиксом длины, как в Паскале, то сложность будет O(1), так как достаточно только прочитать хранящееся значение. Если же строка хранится как в C/C++, с нулевым байтом в конце, то сложность будет O(n), так как надо в цикле перебрать все байты строки, пока не найдём ноль.

Answer 2

[Mikhail Osher]

O(1)

const items = {
  foo: 1,
  bar: 2,
}

function getValueByKey(key) {
  return items[key];
}

O(n)

const items = [
  { key: 'foo', value: 1 },
  { key: 'bar', value: 2 },
]

function getValueByKey(key) {
  for (let i = 0; i < items.length; i++) {
    const item = items[i];

    if (item.key === key) {
      return item.value;
    }
  }
}

Comments

[Иван]

Понял, а что на счёт того примера, что привёл я? Он линейный или константный?

[Mikhail Osher]

BenderIsGreat34, константный, ибо нет ни одного цикла. Почитайте про Time Complexity и Space Complexity.
Прочитайте книгу "Грокаем алгоритмы". Она небольшая, и описывает данную тему простым языком.

[Rsa97]

Mikhail Osher,

константный, ибо нет ни одного цикла.

А Array.sort() какую сложность имеет? Снаружи то тоже не видно ни одного цикла.

[Mikhail Osher]

Rsa97, зависит от низлежащего алгоритма. Скорее всего, там QuickSort за O(N * logN)

[Rsa97]

Mikhail Osher, То есть сам факт отсутствия цикла в видимом алгоритме ещё не говорит об O(1), надо знать, как устроен тип String и хранится или вычисляется length.

[Mikhail Osher]

Rsa97, в доках написано "read-only property". Из этого можно предположить, что тут идёт сложность "hash table search", то есть O(1).

[Karpion]

Mikhail Osher, QuickSort имеет сложность O(n^2) в худшем случае.

"hash table search" тоже имеет нетривиальную формулу для времени работы. В худшем случае (когда много коллизий) там всё очень плохо.

[Mikhail Osher]

Karpion, худший случай рассматривают только в университетах и на интервью в гугл. В обиходе все оперируют average.

[Karpion]

Mikhail Osher, У меня ощущение, что слово "RTOS" Вам не знакомо.

Также Вам незнакома мат.статистика - иначе бы Вы понимал, что слово "среднее" здесь употреблять нельзя до тех пор, пока Вы не выяснили распределение величины, от которой берёте среднее.

Answer 3

[Robur]

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

C чего вы взяли? какая разница в скорости будет если length = 1 и length = 1000000?
Алгоритм в примере просто берет значение из переменной Length и возвращает его.
"Взять значение переменной" всегда одно и то же действие. И сложность этого действия - одинаковая.

Comments

[Иван]

Robur я видимо неверно понимаю принцип работы метода length, он не делает перебор всех элементов в массиве с целью подсчёта количества?

[Karpion]

BenderIsGreat34, Именно так. Количество элементов в массиве - хранится в ещё одном элементе, но не массива, в структуры, содержащей массив.

Я как бы намекаю, что то, что Вы назвали словом "массив" - это не просто массив (в понимании Си), а структура, которая содержит массив и ещё какие-то вещи, нужные для работы (в т.ч. - количество элементов массива).

[Robur]

BenderIsGreat34,
понятия не имею как работает length - вы даже не указали что это за язык. В любом случае это детали реализации и такие вещи всегда оптимизируют. Он может даже по разному работать с разными данными или с разными ключами компиляции.

В целом тут не важно как работает length - в данном примере, с точки зрения алгоритма работы GetCount - это просто одна единственная операция "взять значение".

В те моменты когда реализация имеет значение - это обговаривается и указывается явно.