Является ли вложенный цикл автоматически O (n ^ 2)?

Question

Мне недавно задали вопрос на собеседовании о проверке действительности доски Судоку. Основной ответ включает в себя for петли. По существу:

for(int x = 0; x != 9; ++x)    
    for(int y = 0; y != 9; ++y)
        // ...

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

Позже меня спросили о сложности этого кода. Честно говоря, насколько я понимаю, все ячейки доски посещаются ровно три раза, поэтому O(3n). Для меня тот факт, что у нас есть вложенные циклы, не означает, что этот код автоматически O(n^2) или even O(n^highest-nesting-level-of-loops). Но у меня есть подозрение, что это ответ, который ожидал интервьюер ...

По-другому, какова сложность этих двух частей кода:

for(int i = 0; i != n; ++i)
    // ...

и

for(int i = 0; i != sqrt(n); ++i)
    for(int j = 0; j != sqrt(n); ++j)
        // ...

Answer 1

Ваша общая интуиция верна. Давайте немного поясним обозначение Big-O:

Big-O дает верхнюю границу сложности наихудшего (времени) для вашего алгоритма по отношению к n - размеру вашего ввода. По сути, это измерение того, как объем работы изменяется в зависимости от размера ввода.

Когда вы говорите что-то вроде

все ячейки доски посещаются ровно три раза, поэтому O (3n).

вы подразумеваете, что n (размер вашего ввода) - это количество ячеек на доске , и поэтому посещение всех ячеек три раза действительно будет O (3n) (что O (n)) операция. Если это так, вы были бы правы.
Однако обычно, когда речь идет о проблемах Судоку (или проблемах, связанных с сеткой в ​​целом), n принимается равным количеству ячеек в каждой строке / столбце (доска n x n). В этом случае сложность среды выполнения будет O (3n²) (что действительно равно O (n²)).
В будущем вполне допустимо спросить вашего интервьюера, что n равно .

---

Что касается вопроса в заголовке (Является ли вложенный цикл автоматически O (n ^ 2)?) краткий ответ - нет .
Рассмотрим этот пример:

for(int i = 0 ; i < n ; i++) {
    for(int j = 0 ; j < n ; j * 2) {
       ... // some constant time operation
    }
}

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

---

В ваших примерах, в первом случае у вас есть один цикл for, который делает n итераций, следовательно, сложность (по крайней мере) O (n) (операция выполняется порядка n раз ).
Во втором случае вы вложили в циклы, каждый из которых выполняет sqrt (n) итераций, поэтому общая сложность времени выполнения (по крайней мере) O (n) также. Вторая функция не является автоматически O (n ^ 2) просто потому, что она содержит вложенный цикл. Количество выполняемых операций по-прежнему одного и того же порядка (n), поэтому эти два примера имеют одинаковую сложность - , поскольку мы предполагаем, что n одинаково для обоих примеров .
Это самый важный момент, чтобы плыть домой. Чтобы сравнить производительность двух алгоритмов, вы должны использовать один и тот же вход для сравнения. В вашей задаче судоку вы могли бы определить n несколькими различными способами, и способ, которым вы это сделали, напрямую повлиял бы на вычисление сложности задачи - даже если объем работы все тот же.

* ПРИМЕЧАНИЕ - это не связано с вашим вопросом, но в будущем избегайте использования != в условиях цикла. Во втором примере, если log (n) не является целым числом, цикл может выполняться вечно, в зависимости от языка и его определения. Поэтому рекомендуется использовать < вместо.

Answer 2

Это зависит от того, как вы определяете так называемые N.

Если размер доски N-на-N, то да, сложность O (N ^ 2).

Но если вы скажете, что общее количество сеток равно N (т. Е. Идентификатор платы sqrt (N) -by-sqrt (N)), то сложность равна O (N) или 3O (N)если вы не возражаете против постоянной.