Просто быстрый вопрос:Средняя сложность случая - расчет линейного алгоритма
Если у меня есть линейный алгоритм поиска (который будет проходить через каждый элемент раз до определенного условия), как я могу вычислить среднюю сложность дела для n = 500? Худший случай и лучший случай прост.
Средний случай аналогичен простому: до тех пор, пока предметы, которые вы находите, уникальны, в среднем вам придется искать полпути через список + 0,5.
Предположим, что вы просматриваете каждый элемент в списке один раз. Когда вы просматриваете первый элемент, вам нужно будет осмотреть 1 предмет. Когда вы просматриваете второй пункт, вам нужно будет проверить 2 элемента и так далее. Общее количество проверок составляет
1 + 2 + 3 + ... + 500 = 125250
Таким образом, с 500 поисковыми запросами вы будете обследованы 125250 предметов. В среднем это 250,5 проверок на поиск.
Если ваши шаблоны поиска неравномерны, то это исказит ваш средний случай (например, если вы чаще просматриваете предметы в начале списка или повторяете некоторые предметы и находите любое из них)
Да, это то, что я думал, но я помню, почему-то мой учитель сказал, что во время лекции было не правильно. Однако для меня это имеет смысл. Благодаря! – user1062704
То, что меня удивило, когда я действительно вычислял сложность, состоит в том, что ответ составляет 250,5 вместо 250. – tfinniga
Если это вас удивляет, просто вспомните формулу для суммы базовых арифметических рядов (1 + 2 + ... + n) , Это (количество терминов) * (первый член + последний член)/2. Поскольку вы делите эту сумму на количество терминов, то, что вы вычисляете, справедливо (первый член + последний член)/2. В этом случае (500 + 1)/2 – Shashank
Средняя сложность случая алгоритма линейного поиска равна n + 2 где n - количество элементов в списке.
Если он рассчитывает линейно, разве это не будет 250? – joshstrike