улучшить сложность текущего времени - PullRequest
Новая
       4

улучшить сложность текущего времени

0 голосов
/ 30 марта 2020

Мне дали эту проблему в интервью. Я смог сделать это с помощью вложенного подхода l oop. Мне было интересно, есть ли лучший способ сделать это?

API даны - getFriends (person): он возвращает количество друзей на человека. - getItems (person): возвращает предметы, купленные человеком.

Проблема: вернуть список предметов, которые были куплены друзьями человека, из наиболее купленных в наименее купленные. 

function getList(person)
{
    var itemsMap = {};
    var friends = getFriends(person);
    for(var i = 0 ; i < friends.length; i++)
    {
       var items = getItems(friends[i]);
       for(var j = 0 ; j < items.length; j++)
       {
         if(!itemsMap[items[j]])
             itemsMap[items[j]] = 1;
         else
             itemsMap[items[j]] = itemsMap[items[j]] + 1;
       }
    }

    var res = [];

    itemsMap.sort();

    for(item in itemsMap)
        res.push(item);


    return res;
}

1 Ответ

1 голос
/ 31 марта 2020

Узким местом в вашем коде является не двойное l oop. Вы должны go по всем пунктам, и это именно то, что вы делаете.

Узким местом является сортировка, которая может быть O((n*m)log(n*m)) - где n - это число "друзей", а m - это среднее количество предметов на друга.

Это можно сделать, однако, в O(n*m), выбрав мудрую сортировку (например, сортировка ведра ) или даже отсортировав элементы по мере необходимости. сборка itemsMap.

Причина, по которой вы можете получить более высокую производительность, чем обычная сортировка, заключается в том, что размер каждого элемента ограничен, а сумма всех этих элементов составляет самое большее n*m.

...