none
В каждом случае необходимо оценить сложность полученного алгоритма, использование памяти (т.е. оценить О())? RRS feed

  • Вопрос

  • Здравствуйте, оцените пожалуйста 3 алгоритма в подробных решениях Big O Notation:
    Dictionary<int, dict> dict = new Dictionary<int, dict>();
                dict.Add(1, new dict() { TingsTitle = "первая" });
                dict.Add(2, new dict() { TingsTitle = "вторая" });
                dict.Add(3, new dict() { TingsTitle = "третья" });
                dict.Add(4, new dict() { TingsTitle = "четвертая" });
                dict.Add(5, new dict() { TingsTitle = "пятая" });
                for (int i = 6; i < 50; i++)
                {
                    dict.Add(i, new dict() { TingsTitle = "число"+i }); 
                }
    
                foreach (var a in dict )
                {
                    Console.WriteLine("Кллюч: {0}, TingsTitle: {1}", a.Key, a.Value.TingsTitle);
                }
                Console.WriteLine(new string('-', 50));  
    
    
    
    //1
    
                Console.Write("Ищем LINQ: ");
                string val = Convert.ToString(Console.ReadLine()); 
                var tr = dict.Values.Where(c => c.TingsTitle.Contains(val)).Select(c => c.TingsTitle).ToList(); 
                if (tr != null) {
                    foreach (var b in tr)
                    {
                        Console.WriteLine("нашел: " + b);
                    }
                }
                Console.WriteLine(new string('-', 50));  
    //2
    Console.Write("Ищем по структуре KeyValuePair: ");
                string val3 = Convert.ToString(Console.ReadLine());
                foreach (KeyValuePair<int, dict> kvp in dict)
                {
                    if (kvp.Value.TingsTitle.Contains(val3))
                    {
                        Console.WriteLine(kvp.Value.TingsTitle);
                    }
                }
                Console.WriteLine(new string('-', 50));  
    //3
        
    Console.Write("Введите ключ от 1 до 5: ");
                int key = Convert.ToInt32(Console.ReadLine());
                bool tr3 = dict.ContainsKey(key);
                if (tr3)
                {
                    Console.WriteLine("нашел: " + dict[key].TingsTitle);       
                }
                Console.WriteLine(new string('-', 50));  
    
                Console.ReadKey();

    • Изменено A1x1On 10 июня 2015 г. 8:44
    10 июня 2015 г. 6:48

Ответы

  • В первом и втором случае вы ищете значение в Values, в третьем - в Keys. Сравнивать их нет смысла, имхо.

    И в первом, и во втором случае происходит проход по всей коллекции. Следовательно O(n). Причём в первом случае проход будет не один, но сложности это не меняет, всё равно O(n).

    В третьем случае поиск по ключу - O(1).

    Надеюсь не ошибся. Интересно мнение других форумчан.

    10 июня 2015 г. 9:36
  • Хмм... А хрен его знает! Это точный ответ.

    Понимаете ли, вы не указали ни используемый язык (я лишь могу предположить, что это C#), ни точный тип используемой коллекции (опять же, я лишь предполагаю, что это System.Collections.Generic.Dictionary). Поэтому - хрен его знает.

    ---

    Если я угадал тип коллекции, то поиск по ключу всегда O(1). Смотрите раздел Заметки. В следующий раз сперва читайте документацию; я не собираюсь работать за вас Гуглом.

    Сколько расходует памяти? Хэш-таблица сложная структура данных (лучше читайте английскую версию, если владеете языком - там намного больше информации). Размер потребляемой памяти может сильно варьироваться в зависимости от количества корзин (бакетов), что в свою очередь зависит от хэш-функции и помещаемых в словарь элементов.

    Также нужно понимать, что в случае ссылочных типов любая коллекция хранит лишь ссылки, а сами объекты будут в куче. Если хочется замерить абстрактное потребление памяти, то можно так.

    ---

    Вот список разных структур данных для общего развития. (Помню, раньше был подобный список на русском в Википедии, почему-то удалили).

    11 июня 2015 г. 10:11

Все ответы

  • В первом и втором случае вы ищете значение в Values, в третьем - в Keys. Сравнивать их нет смысла, имхо.

    И в первом, и во втором случае происходит проход по всей коллекции. Следовательно O(n). Причём в первом случае проход будет не один, но сложности это не меняет, всё равно O(n).

    В третьем случае поиск по ключу - O(1).

    Надеюсь не ошибся. Интересно мнение других форумчан.

    10 июня 2015 г. 9:36
  • Галиматья полнейшая!
    Я и в предыдущем Вашем топике не понял, что такое 
    Dictionary<int, dict> dict = new Dictionary<int, dict>();
    и здесь то же самое.
    Если это словарь словарей, в котором нужно что-то найти,
    так Вы потрудитесь расписать, что это за словари, и что Вы хотите найти.
    А вообще поиск по ключу - это то, ради чего и создан словарь.
    Выборка по value всегда менее эффективна и, к тому же, неоднозначна -
    могут быть записи с разными ключами и одинаковыми значениями.
    Которое Вам необходимо - первое, последнее, или еще какое-либо?
    10 июня 2015 г. 15:21
  • Спасибо, пользуясь случаем, не подскажите как узнать и или просто сколько расходует памяти Dictionary? 
    И как можно сделать, чтобы худшая оценка скорости была O(1), т.е. не зависела от количества слов в словаре? 
    11 июня 2015 г. 8:54
  • Хмм... А хрен его знает! Это точный ответ.

    Понимаете ли, вы не указали ни используемый язык (я лишь могу предположить, что это C#), ни точный тип используемой коллекции (опять же, я лишь предполагаю, что это System.Collections.Generic.Dictionary). Поэтому - хрен его знает.

    ---

    Если я угадал тип коллекции, то поиск по ключу всегда O(1). Смотрите раздел Заметки. В следующий раз сперва читайте документацию; я не собираюсь работать за вас Гуглом.

    Сколько расходует памяти? Хэш-таблица сложная структура данных (лучше читайте английскую версию, если владеете языком - там намного больше информации). Размер потребляемой памяти может сильно варьироваться в зависимости от количества корзин (бакетов), что в свою очередь зависит от хэш-функции и помещаемых в словарь элементов.

    Также нужно понимать, что в случае ссылочных типов любая коллекция хранит лишь ссылки, а сами объекты будут в куче. Если хочется замерить абстрактное потребление памяти, то можно так.

    ---

    Вот список разных структур данных для общего развития. (Помню, раньше был подобный список на русском в Википедии, почему-то удалили).

    11 июня 2015 г. 10:11
  • Нужно экспериментировать!
    Я обычно пишу несложную программку,
    в которой засекаю время начала,
    затем в цикле обращаюсь к заранее заготовленной болванке, т.е. исследуемой функции.
    Болванкой может быть что угодно - сложение, умножение, обращение к словарю, и т.д.
    Обращений должно быть достаточно много - 1000, 1.000.000, 1.000.000.000,
    в зависимости от болванки.
    В конце цикла отсекаю время и нахожу быстродействие исследуемой функции.
    Это могут быть микросекунды, или миллисекунды, или наносекунды.

    Вот посмотрите сюда. Меня это тоже интересовало.
    11 июня 2015 г. 10:26