Пока Гвидо ван Россум делал Питон списком смежности называли и такое, нпр., представление полного графа из 3 вершин: 1-2, 2-3, 3-1.
Нпр., и после Питона я написал:
Такой подход соответствует одному из наиболее экономных представлений графа в виде списка смежности. В частности, он очень удобен для ручного ввода графов. Можно использовать следующий формат для записи ребра:
v-u
где v,u – инцидентные ребру вершины.
Возражений не последовало )
Обход ребер для одной вершины — внутренний список. Обход для всех ребер — перебор вершины — внешний цикл.
Число всех вершин — m, число ребер — n. Допустим наиболее экономную по времени ситуацию, когда в списках нет повтора ребер, как в приведенном примере: 1-2, 2-3, 3-1 — первое число вершина, для которой список, вторая список (в примере они из одного элемента). Обработка всех списков по внутреннему циклу даст kn операций, но внешний цикл перебора вершин — это еще pm операций, где k,p константы, зависящие от реализациии. Т.о. получим O(kn+pm). Однако пока не очевидно, что обсуждаемый алгоритм эквивалентен алгоритму со списком смежности графа.
достаточно крутить цикл от 1 до N, проверяя каждое i на «Эратосфенность», и складывая истинные результаты в массив, дерево или список
Нужно помнить вычеркнутые числа. Иначе вычеркнули кратные 7 в одном цикле, далее опять их же будем проверять на кратность 11, где они не все вычеркнуться? Такое работать не будет.
Внешний цикл перебирает все вершины. Внутренний перебирает все ребра
Пусть в графе m вершин и n ребер. Граф задан матрицей смежности
g : array [1..m,1..m] of boolean;
где g[i,j] = true, если существует ребро (i,j), false — в противном случае. Поставим простейшую задачу: перебором пар вершин удалить все ребра.
Решение:
for i:=1 to m do
for j:=1 to m do
g[i,j] := false;
Сложность O(m^2), от n не зависит.
Если мы хотим реагировать только на существующие ребра, то можем написать:
for i:=1 to m do
for j:=1 to m do
if g[i,j] then
g[i,j] := false;
Сложность не изменится, хотя оператор g[i,j] := false; будет выполняться ровно m раз в случае несимметрической матрицы и 2m раз в случае симметрической.
В псевдокоде действителбную сложность можно попытаться замаскировать:
для i от 1 до m
для j: (i,j) существует, j<=m
g[i,j] := false;
Можно работать только с половиной матрицы выше (или ниже) главной диагонали, но это для наших рассуждений не принципиально.
Спасибо. Я примерно представил, что Вы хотите сказать, но, к сожалению, то что Вам удалось сказать звучит как-то слишком расплывчато (с учетом того, что сказано в упомянутых источниках). М.б., если поднять первоисточник, то там всё это показано достаточно строго. Можно предположить, что авторы вторичных источников разобрались в первичном, но при пересказе опустили важные моменты, сделав вид, что эти моменты очевидные. Такое, к сожалению, случается с нетривиальными алгоритмами. В результате четкое наглядное доказательство превращается в запутанный ребус. Однако читатель не должен разгадывать ребусы. В мат.журналах существует строгое правило: чтение производится до первой ошибки или неясности. При этом, конечно, встречаются и очень покладистые читатели, которые готовы верить каждому «печатному слову» — им только кажется, что они всё поняли.
Прежде всего возникает вопрос: а зачем тогда внутренний цикл?
внутренний цикл точно дойдет до k
Сколько шагов он будет доходить? Не будет ли он работать вхолостую подбирая нужное значение? Не зависит ли это от реализации?
PS BTW Пожалуйста, подскажите, кто знает: как на Хабре оформлять псевдокод? Установил «source lang=code» пропали отступы, установил «delphi» фигурные скобки стали комментами.
А проблема заключалась ровно в том, что ФП не очень хорошо подходит для реализации РЭ, как и для многих других нетривиальных алгоритмов.
В том обсуждении был сделан аналогичный вывод. Т.о. РЭ помогло выявить важную проблему технологии программирования (ФП):
Для многих задач в этой парадигме можно сделать очень простой и понятный код. Для других задач чистое ФП все-таки не так хорошо подходит.
Я кидал ссылку на параграф, там описание модификации, но кода нет.
Про какой параграф речь? Если про РЭ с «линейным» временем — там псевдокод:
Вход: натуральное число n
Пусть pr - целочисленный массив, поначалу пустой;
lp - целочисленный массив, индексируемый от 2 до n, заполненный нулями
для i := 2, 3, 4, ..., до n:
если lp[i] = 0:
lp[i] := i
pr[] += {i}
для p из pr пока p ≤ lp[i] и p*i ≤ n:
lp[p*i] := p
Выход: все числа в массиве pr.
советую в нем разобраться.
Код (см. Реализация) почти аналогичен псевдокоду в вики. И как, скажите, пожалуйста, два вложенных друг в друга цикла (первый от 2 до n) могут дать линейное время?
Думаю, что здесь есть «стилистическая» ошибка от авторов статьи в вики,
И где там последовательность (3)? И почему оптимизированной реализацией назван другой вариант? Приведенная там последовательность (Листинг 1 у меня) избыточна.
чтобы определить, является ли число НЕпростым, достаточно проверить его делимость на несколько первых ПРОСТЫХ чисел в последовательности.
Не только первых. Пусть на каком-то шаге имеем максимальное для данного шага простое число М. Конструируем из него непростое число, не содержащее меньших делителей — это будет М в квадрате.
Слышал об обратном случае преувеличенной заботы о ресурсах. Во времена IBM PC AT в редакцию одного солидного н-т. журнала серьезные вроде бы авторы прислали описание своей прикладной программы, где особой заслугой отмечалась реализация обработки событий мыши на ассемблере. На недоуменный вопрос редактора, а почему на ассемблере, было уверенно отвечено, что на высоком ЯП быстродействия может не хватить. В редакции, когда обсуждали, кто-то предположил, что может они не рукой мышь двигают, а из пневмопушки ей стреляют, чтобы катилась быстрей.
Буду, нпр., искать грант на покупку/аренду нужного железа ;)
Много лет назад участвовал в международном конкурсе Интел (не для студеньов, а дл профи). Все задачи были на грани возможностей тогдашнего железа.
Но задача формулируется не как «нагрузочное тестирование, на примере решета эратосфена», а именно как поиск простых чисел.
Нпр., и после Питона я написал:
Возражений не последовало )
Число всех вершин — m, число ребер — n. Допустим наиболее экономную по времени ситуацию, когда в списках нет повтора ребер, как в приведенном примере: 1-2, 2-3, 3-1 — первое число вершина, для которой список, вторая список (в примере они из одного элемента). Обработка всех списков по внутреннему циклу даст kn операций, но внешний цикл перебора вершин — это еще pm операций, где k,p константы, зависящие от реализациии. Т.о. получим O(kn+pm). Однако пока не очевидно, что обсуждаемый алгоритм эквивалентен алгоритму со списком смежности графа.
Сложность O(n).
где g[i,j] = true, если существует ребро (i,j), false — в противном случае. Поставим простейшую задачу: перебором пар вершин удалить все ребра.
Решение:
Сложность O(m^2), от n не зависит.
Если мы хотим реагировать только на существующие ребра, то можем написать:
Сложность не изменится, хотя оператор g[i,j] := false; будет выполняться ровно m раз в случае несимметрической матрицы и 2m раз в случае симметрической.
В псевдокоде действителбную сложность можно попытаться замаскировать:
Можно работать только с половиной матрицы выше (или ниже) главной диагонали, но это для наших рассуждений не принципиально.
Прежде всего возникает вопрос: а зачем тогда внутренний цикл?
Сколько шагов он будет доходить? Не будет ли он работать вхолостую подбирая нужное значение? Не зависит ли это от реализации?
В том обсуждении был сделан аналогичный вывод. Т.о. РЭ помогло выявить важную проблему технологии программирования (ФП):
Про какой параграф речь? Если про РЭ с «линейным» временем — там псевдокод:
Код (см. Реализация) почти аналогичен псевдокоду в вики. И как, скажите, пожалуйста, два вложенных друг в друга цикла (первый от 2 до n) могут дать линейное время?
И я так думаю. О чем и сказал в статье.
Я не вижу, как это можно сделать. Попробуйте.
Буду, нпр., искать грант на покупку/аренду нужного железа ;)
Много лет назад участвовал в международном конкурсе Интел (не для студеньов, а дл профи). Все задачи были на грани возможностей тогдашнего железа.
Но цель поиска в формулировке отсутствует.
Бенчмарк нужен и для выявления возможности таких накладок. Когда подобное недопустимо меняют конфигурацию или систему.