Как рассчитать временную сложность этого странного метода

Метод:Как рассчитать временную сложность этого странного метода

List<Book> books = new List<Book>(); 

public List<Book> Shoot() 
{ 
    foreach(var b in books) 
    { 
     bool find = true; 
     foreach(var otherb in books) 
     { 
      if(otherb != b && otherb.Author == b.Author) 
      { 
       find = false; 
      } 
     } 

     if(find) 
     { 
      yield return b; 
     } 
    } 
}

Обычно временная сложность будет O (books.Count^2), но есть если (найти) заявление во внешнем цикле, и это может изменить время цикла.

Так что мои вопросы:

Какова временная сложность этого метода?
Как вы его вычислили?

Я жду ответа в Интернете.

Благодарим вас заблаговременно.

источник

2012-06-29 Franva

Переменная 'find' изменяет время работы не более чем на O (books.Count), что меньше O (books.Count^2). Поэтому общая сложность все еще O (books.Count^2). –

Две вложенные петли, большие oh n x n. Сортировка по автору, если вы хотите сделать это счастливее. –

Я не уверен, что это имеет значение, но, вообще говоря, вложенные петли, которые вы обнаружите при выполнении сортировки зависимостей, но если они обнаружены за пределами подозрительных. Я просто не уверен, что вопрос: «Какова временная сложность, насколько это так», что мы действительно пытаемся сделать здесь, и, возможно, мы сможем сделать это намного лучше ». Если вы хотите, дайте мне знать, что бизнес просит от вас, и, возможно, мы сможем найти более упрощенный способ. –

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

Возврат доходности не изменит сложность алгоритма, он создаст шаблон итератора, но если вы пройдете весь список из вызывающей функции, вы пройдете все итерации в своем алгоритме.

What is the yield keyword used for in C#?

Для оптимизации алгоритма, так как btilly говоря, вы могли бы сделать два прохода по коллекции, на первом проходе вы храните количество книг на автора в хэш-таблице и на втором проходе вы проверить если автор имеет более чем одну книгу, используя хэш-таблицу (предполагая, что постоянное время для поиска) и дают книгу, если она делает:

public List<Book> Shoot() 
{ 
    var authors = new Dictionary<string, int>(); 
    foreach(var b in books) 
    { 
     if(authors.ContainsKey(b.Author)) 
      authors[b.Author] ++; 
     else 
      authors.Add(b.Author, 1); 
    } 

    foreach(var b in books) 
    { 
     if(authors[b.Author] == 1) 
      yield return b; 
    } 
}

Таким образом, у вас есть линейное время сложность O (N), примечание что в этом случае вам понадобится дополнительное пространство O (n).

источник

2012-06-29 00:26:43 Jaime

Лучший случай не намного лучше, потому что внутренний цикл не прерывается. он всегда выполняет полные n итераций. –

Обычно нас интересует средний случай, а не худший случай. Не верьте мне? Вы думаете о поиске хэша как 'O (n)' или 'O (1)'? Является ли quicksort 'O (n * n)' или 'O (n log (n))' в вашем мире? (Да, я знаю, что вы можете сделать худший случай лучше, чем те, но реалии реального мира обычно этого не делают.) – btilly

@ Раймонд правильно, лучшим случаем будет 1 петля во внешнем одном + n раз во внутреннем цикле – Jaime

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

Обычно (но не всегда!) Людей больше всего интересует средний случай.

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

источник

2012-06-29 00:38:15 btilly

Как рассчитать временную сложность этого странного метода

ответ

Смежные вопросы