Выяснение отношения Big O Notation / Recurrence от моего старого алгоритма

Question

Выяснение отношения Big O Notation / Recurrence от моего старого алгоритма

1

** Привет всем, У меня есть вопрос о возврате отношения /Big O обозначение. Мне было задано задание на домашнее задание, в котором я попросил передать ноту Big O некоторых из моих старых кодов/алгоритмов, которые я придумал для предыдущих заданий домашней работы. К сожалению, я еще не прошел курс по конечной математике; так что это ново для меня. Мне удалось выяснить три из четырех алгоритмов, которые я использовал. Однако я придерживаюсь четвертых алгоритмов. Этот метод является рекурсивным методом и кодируется на Java. Я действительно потратил часы, пытаясь понять это, и я смотрел множество видеороликов и читал множество статей по нотации Big O, но, к сожалению, не смог их получить. Любая помощь будет отличной !!! Вот код:

ArrayList<FacebookUser> getRecommendations(FacebookUser e) {
    FacebookUser rootUser = userCallForList.get(0);


    if(rootUser.getFriends().isEmpty() || e.getFriends().isEmpty()){
        return returnHash();
    }

    for(FacebookUser hold : e.getFriends()){
        if( !hold.equals(rootUser) && addHash(hold)){
            getRecommendations(hold);   
        }
    }

    return returnHash();
}

Примечание. О коде: метод принимает FacebookUser в качестве аргумента. Метод возвращает ArrayList, который содержит всех друзей FacebookUser, которые передаются ему, а также результат вызова одного метода getRecommendations для всех этих друзей FacebookUsers. Он не добавляет кого-либо в список рекомендаций, если они уже находятся на нем, и не добавляет к нему FacebookUser (EI rootUser); Так как это может привести к бесконечному циклу. Я использую HashSet как свою коллекцию, а затем я должен изменить ее обратно на ArrayList.

Nat 19 март 2015, в 21:36

Источник

Теги:

java

recursion

big-o

recurrence

1 ответ

Ещё вопросы

Tulsi Leathers · Accepted Answer · 2015-03-19T19-24-00.000Z

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

Это утверждение

for(FacebookUser hold : e.getFriends()){
        if( !hold.equals(rootUser) && addHash(hold)){
            getRecommendations(hold);   
        }
    }

вызывает getRecommendations() для неуказанного количества друзей, которое затем вызывает его для каждого друга друзей. Мне кажется, что этот метод будет вызываться для каждого друга в сети или на каждом узле, если вы думаете об этом как о проблеме с графом. Это означает для меня время работы O (k), где k = количество уникальных узлов, доступных от начального пользователя любым количеством ребер.

Большое спасибо, что нашли время ответить на мой пост; Я также согласен, что это не алгоритм «разделяй и властвуй». Теперь я думаю, что Big O Notation - это O (N + M), потому что два набора данных (число FacebookUser и количество друзей) вместе определяют производительность. И после запуска этого кода с разным количеством FacebookUser у каждого было разное количество друзей. Я обнаружил, что сложность времени зависит от двух факторов: количества пользователей FacebookUser, вовлеченных в рекурсивный вызов, и размера каждого списка друзей FacebookUsers.
Я думаю, что это хуже, чем O (k) из-за returnHash() выполняющего преобразование из хэш-набора в список массивов при каждом вызове. В зависимости от того, как именно выполняется это преобразование, вы можете говорить O (k ^ 2).
Преобразование выполняется для каждого цикла, и я думаю, что это происходит при каждом возврате. public ArrayList<FacebookUser> returnHash() { ArrayList<FacebookUser> returnList = new ArrayList<FacebookUser>(); for (FacebookUser hold : glo) { returnList.add(hold); } return returnList; }
Принимая во внимание, что теперь кажется, что returnHash () занимает n времени. Я думаю, что тогда время будет O (n + m ^ 2), где n = начальное количество пользователей Facebook, а m среднее число друзей / пользователя?
Не уверен, что m - это среднее число друзей / пользователей. Например, если a, b, c, and d являются FacebookUser и --> означают, что они являются друзьями. a --> bb --> c c --> dc --> b c--> a d --> ad --> b Число пользователей Facebook, участвующих в рекурсивном методе, равно 4, а общий размер всех друзей 7. Если n количество задействованных пользователей Facebook, а m - общий размер всех друзей. Однако, если мы сделаем O (n + m ^ 2), общая сложность времени будет только (4+1.75^2) = 7.0625 что не имеет смысла. Извините за плохое написание по телефону ..