Может ли быть более одного ответа на сложность Big O?

Question

Как бы вы говорили о следующей функции с точки зрения сложности Big O?

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n && j < 10; j++) {
    //do something in constant time
  }
}

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

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

Теперь, если вы переключаетесь на вектор или хэш-карту (я бы сказал, просто использоватьмассив целых чисел, но пример, который кто-то использовал, был hashmap), вы получаете переменный размер до 128 символов.

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

Я никогда не слышал об использовании «лимитов» при работе с Big O. Так что же правильно в этом случае?Правильно ли я в том, что правильная сложность при оценке большой O должна учитываться только тогда, когда n "достаточно большой"?Или есть другие случаи, когда могут быть альтернативные ответы?

Answer 1

Может ли быть более одного ответа?

Да, большая нотация O выражает что-то вроде "меньше или равно", поэтому, если ваше усилие в O (n), оно такжев O (n log n) или в O (n ^ 2).Однако обычно нас интересует жесткая граница.

Давайте поговорим о сложности определения размера, если две строки являются перестановками друг друга

Набор возможных символовв строках конечно, поэтому размер сложности в O (1).В свете того, что я сказал ранее, это также в O (n);но более узкая граница - O (1).

Answer 2

В вашем сообщении есть несколько вопросов.Кроме того, они не являются действительно вопросами программирования.Я постараюсь дать полезный ответ:

Цикл есть и в O(n), и в O(n^2) (пожалуйста, прочитайте об определении Big-Oh, Wikipedia, например).Цикл также будет O(n^3) или O(n^4), если хотите.Но идея состоит в том, чтобы найти «низший» O(f(n)), который в вашем случае будет O(n), а точнее O(10*n), который на самом деле равен set и O(n).

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

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