Что такое Большой Θ-анализ этой функции?

public SomeObject secondFunction(SomeObject obj) {

    SomeObject retVal = new SomeObject

    for data in this.dataCollection {
        for data2 in obj.dataCollection {
            if(someCondition) { 
                retVal.add(data) 
            }
        }
    }

    return retVal
}

Я пытаюсь изучить алгоритм анализа. Что такое анализ Big Θ реализации этой функции? Почему как?

Я не думаю, что это алгоритм n-квадратов, поскольку две зацикленные структуры, возможно, имеют разные размеры. Интуитивно я хочу назвать его алгоритмом n*m, поскольку количество элементов в obj,dataCollection и this.dataCollection неизвестно. Но я никогда не видел, чтобы эта фраза использовалась раньше, поэтому, вероятно, она неверна. Что это такое?

Кроме того, что мы можем сказать о лучшем, худшем и среднем случаях? Кажется, что лучший и худший случаи одинаковы, так как он каждый раз будет перебирать все элементы в обеих структурах. Это правильно или неправильно? Кроме того, что это означает для среднего случая? Будет ли средний случай таким же, как лучший и худший случай в этом конкретном примере?


algorithm big-o big-theta
person Philosobot    schedule 13.04.2015    source источник
comment
@Lashane - Спасибо за комментарий. Почему/как O(nk)=O(n^2)=Θ(N^2), когда k может быть намного больше или меньше, чем n?   -  person Philosobot    schedule 13.04.2015
comment
представьте, что N -> бесконечность и K -> бесконечность, поэтому lim(N*K) = N^2   -  person Iłya Bursov    schedule 13.04.2015
comment
@Lashane: Нет, Θ(N^2) определенно не совпадает с Θ(N*K). Существует точное математическое определение того, что означает Θ(N*K), и функция, равная Θ(N*N), ему не удовлетворяет.   -  person psmears    schedule 13.04.2015
comment
@psmears это не то же самое, но обычно мы используем только N для описания O, Θ и т. д., поэтому мы можем предположить, что N=K=max(N,K), и поэтому Θ(N*K)=Θ(N ^2)   -  person Iłya Bursov    schedule 13.04.2015
comment
@Lashane: для f = O (M * N) допустимо заменить max (N, K), чтобы получить f = O (max (N, K) ^ 2), потому что O () дает верхнюю границу (с точностью до постоянный фактор), поэтому замена большей верхней границы не делает утверждение ложным. Это неверно для Θ, который дает верхнюю и нижнюю границу (опять же, с точностью до постоянного множителя), поэтому подстановка строго большей функции неверна.   -  person psmears    schedule 13.04.2015

Ответы (1)


arrow_upward
1
arrow_downward

Ваша интуиция верна - ее можно назвать реализацией Θ(n * m), предполагая, что тело внутреннего цикла занимает постоянное время (и что время для выполнения фактической итерации незначительно).

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

person psmears    schedule 13.04.2015
comment
Спасибо за комментарий. Пара дополнений: (1) Предположим, что функция добавления выполняет некоторую операцию сортировки, когда добавляет ее в retVal. Препятствует ли это тому, чтобы в теле цикла было постоянное время, поскольку мы не знаем, сколько времени это займет? (2) Если условие во внутреннем операторе if проверяло retVal, чтобы увидеть, содержит ли оно значение (и мы не знаем, сколько шагов это занимает), то препятствует ли это постоянному времени внутри цикла тело? (3) Если да на любой из этих вопросов, как это повлияет на анализ большого Θ? - person Philosobot; 13.04.2015
comment
(1) Это зависит от того, что он сортирует! Если он сортирует список постоянного размера, время должно быть постоянным; если он сортирует элементы, добавленные до сих пор, то нет, и вам придется учитывать время, затраченное на сортировку, в общем анализе сложности. (2) Опять же, это зависит. Некоторые тесты могут быть постоянными; некоторые могут зависеть от размера проблемы. (3) Опять же, это зависит - но обычно вам придется умножать время, затрачиваемое на эти две операции, на вашу общую сложность - поэтому, если бы одна из них была, скажем, Θ (log N), то вы могли бы получить общее время Θ (N*K*log N) - person psmears; 13.04.2015
comment
Еще раз спасибо за комментарии. У меня все еще есть последний вопрос о (2) и (3). В одном алгоритме, который я анализирую, он проверяет, были ли данные уже добавлены в retVal, прежде чем добавить их. Так что замените someCondition моего кода в выражении if на data.equals(data2) && !retVal.contains(data), где contains перебирает связанный список данных, который мы создали, проверяя наличие вхождений. Это не постоянное время, так как мы не знаем, сколько элементов находится в retVal на каждом заданном проходе, верно? Если это так, то мой вопрос в том, как бы я представил это математически? - person Philosobot; 14.04.2015
comment
Предполагая, что список обычно содержит N * K элементов, а отдельные сравнения занимают постоянное время, это, вероятно, будет Θ (N ^ 2 * K ^ 2). - person psmears; 14.04.2015
comment
Хорошо, это имеет смысл, если список содержит NxK элементов. Однако на самом деле в списке будет неизвестное количество элементов. Я думаю, что он может иметь до N, но может иметь всего 0. Это потому, что он проверяет, находится ли значение в обоих, прежде чем добавлять его (и он не добавляет дубликатов). Обычно он будет иметь что-то в- между этими значениями. Однако отдельные сравнения занимают постоянное время. - person Philosobot; 14.04.2015