Сложность алгоритма, содержащего рандомную операцию

#алгоритм #сложность #асимптотика

Для всякого ли алгоритма можно оценить сложность при помощи О нотации?

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

Ответы

Ответ 1

Да, можно. Следует оценивать с учётом вероятности.

Например, сложность bogosort оценивается как



  я имею массив чисел и хочу вытащить оттуда любое, условно, четное. Но перебирать
их буду не по-порядку, а рандомно, в бесконечном цикле, пока не найду нужное. 


Если в массиве около половины чисел чётные, то O(1).
Если только одно число чётное, то O(n) с жирненькой константой.
Если ни одного, то алгоритм вообще не завершится.

Если рассматривать случайный (равномерный) массив, то, вероятно, будет сводиться
к O(1) - как доступ по ключу хэш-таблицы.

PS: Провёл эксперимент для случая с единственным искомым числом (результат смотреть
в реальной консоли, открытой до запуска сниппета; при запуске браузер может зависнуть
на несколько секунд):



function go(n) {
  while (Math.random() * n | 0);
}

var res = [];

function check(n) {
  var t = performance.now();
  go(1< x+y)
  }
}

console.table(res.map(stat));






При удвоении длины время увеличивается вдвое, т. е. действительно O(n).

P-класс задач и NP- класс задач

#теория #алгоритм #сложность

Объясните пожалуйста как можно подробнее , что такое Р задачи , NP (полные , сложные
..) задачи . А то почитав так и не понял. 
Спасибо заранее    

Ответы

Ответ 1

Смотрите, речь идёт об асимптотической сложности задач. Здесь рассматриваются только
задачи, которые имеют простой однозначный ответ: «да» или «нет». Например, «есть ли
подстрока "XYZ" в данной строке?». Задачи типа «найдите все перестановки данного набора
чисел» как P/NP-проблемы не рассматриваются, так как ответ тут не да/нет.
Алгоритмы часто параметризуются размерами входных данных. Время пробега алгоритма
в общем случае тем больше, чем больше данных ему приходится обрабатывать. Обозначим
n1, n2, ... — параметры, описывающие размеры входных данных, t(n1, n2, ...) — максимальное
время работы алгоритма на данных такой длины.
Если известно, что t(n1, n2, ...) ограничено сверху многочленом от переменных n1,
n2, ..., задача называется решаемой за полиномиальное время. Класс таких задач и обозначается
как P, они считаются вычислительно несложными.
Теперь, что же такое NP-проблема?
Представьте себе, что у вас есть алгоритм с несколькими ветвлениями (if-ами, циклами),
который последовательно тестирует решения, и как только найдёт подходящее, сразу заканчивает
алгоритм с криками «ура, нашёл!» Например, если мы ищем, есть ли символ 'X' в данной
строке, мы можем поочерёдно в цикле проверять, совпадает ли первый символ с X, затем
второй, затем третий, и как только нашли совпадение, заканчиваем работу. Так вот, представьте
себе теперь такую машину, которая магическим образом сразу переходит к нужной итерации
цикла: для поиска символа X в строке "ABCXYZ" она сразу проверяет в 4-ой позиции, то
есть там, где надо! Такая магическая машина называется недетерминированной машиной
(по историческим причинам) и, понятно, не существует в природе.
Так вот, проблема называется NP-проблемой, если она решается за полиномиальное время
на этой самой читерской недетерминированной машине.
Понятно, что всякая P-проблема есть NP-проблема: если уж мы на нормальной машине
решим её за полиномиальное время, то на читерской тем более! Возникает вопрос: а нужно
ли читерство? Может быть, всякая проблема, которая решается на недетерминированной
машине за полиномиальное время, может быть решена и на нормальной тоже за полиномиальное
время?
Это и есть знаменитая P/NP-гипотеза: предполагают, что есть проблемы, которые без
недетерминированной машины за полиномиальное время не решить. Но никто пока не смог
это строго математически обосновать. Проблема тут вот в чём: если мы не умеем решать
какую-то задачу за полиномиальное время, значит ли это, что она в принципе за полиномиальное
время не решается, или мы просто недостаточно умны и изобретательны?

Насколько эффективен мой метод решения?

#python #python_3x #инспекция_кода #комбинаторика #сложность

И вновь всех приветствую. Решил очередную задачу на контесте способом, который показался
мне интересным. Т.к. я новичок, еще не совсем понимаю как определять О(n), поэтому
прошу помощи в этом вопросе.

Собственно, вот сама задача:


  На вход программы поступает последовательность из N целых
  положительных чисел. Рассматриваются все пары различных элементов
  последовательности  (элементы пары не обязаны стоять в
  последовательности рядом, порядок элементов в паре неважен). 
  Необходимо определить количество пар, сумма чисел и разность индексов
  которых кратна 3.


И мое решение:

n = int(input())
summ = 0
r = [[0] * 3 for i in range(3)]
for i in range(n):
    s = int(input())
    r[i % 3][s % 3] += 1
print((r[0][0] * (r[0][0] - 1) + r[1][0] * (r[1][0] - 1) + r[2][0] * (r[2][0] - 1))//2
+ r[0][1] * r[0][2] + r[1][1] * r[1][2] + r[2][1] * r[2][2])


Проверку на контесте прошла, результат - задача решена верно.
    

Ответы

Ответ 1

Решение отличное, сложность линейная от размера ввода

В цикле выполняется k*n операций, где k - константа, так что его сложность O(n)

Начальные строчки выполняются за константное время O(1), финальная тоже, итого

O(n + 1 + 1) = O(n)

Амортизированная константа

#java #cpp #алгоритм #динамические_массивы #сложность

Может кто-нибудь объяснить, что означает амортизированная сложность алгоритма, в
частности, амортизированная константа?
Это когда для массива операция выполняется не каждый вызов, а только один раз?
    

Ответы

Ответ 1

Ну вот смотрите. Берем динамический массив. Сначала из одного элемента.

Добавляем еще один. Удваиваем массив. Итого - одно выделение, один перенос (первого
элемента). 

Еще добавление - массив становится равен 4 элементам. Выделений - 2. переносов -
3 (теперь переносим 2 элемента, + 1 ранее). Добавление четвертого элемента не требует
ни выделения, ни переноса.

Еще добавление. Массив увеличивается до 8 элементов. Теперь в массиве 8 элементов,
3 выделения памяти, 7 переносов элементов. Элементы с 6 по 8 не требуют ни выделения,
ни переноса...

...

Теперь у нас 2n элементов, n выделений памяти, 2n-1 переноса элементов.

Т.е. в среднем каждый элемент пришлось переносить 1-2-n раз, при больших n - 1 раз. 

Константа? Да. При том, что первый элемент переносился log2n раз.

А вот в среднем, т.е. амортизированно - константа.

Так более-менее понятно?

Перевод английского термина “linearithmic” O(N * log N) на русский

#алгоритм #терминология #сложность #перевод

Linearithmic time complexity - линейно-логарифмическая сложность, O(N * log N)

Есть ли какие-то "короткие" переводы слова linearithmic?

Примеры  (выдуманые мной и из комментов) [длинна слова]:


логлинейное             [11]
линеарное               [9]
линлогное               [9]
линарифмическое         [15]
линейнологарифмическое  [22]


Еще варианты?
    

Ответы

Ответ 1

Исходя из того, что термин: Linearithmic не является общепринятым, то есть ну не
Оксфорд, а больше компьютерный сленг, я бы предложил термин логлинейный:


Он конечно не описан в словарях Даля и Ожегова (то есть примерно идентичен linearithmic)
Относительно благозвучен, легко склоняется (в противовес линлогное)
Передает смысл (в противовес линеарное)


Ответ 2

Ставлю на линарифмический.

Потому что "логнейный" звучит гораздо хуже :)

А давайте устроим пари - какой термин первым появится в русскоязычной литературе? :)


  — «Хливкие» — это хлипкие и ловкие. «Хлипкие» значит то же, что и «хилые». Понимаешь,
это слово как бумажник. Раскроешь, а там два отделения! Так и тут — это слово раскладывается
на два!
  (c) Льюис Кэрролл, Алиса в Зазеркалье


Update

В этой книжке встречается линарифмическая сложность :)


Ответ 3

Википедия говорит, что линейно-логарифмическая функция является частным случаем квазилинейной,
так что этот термин тоже можно использовать как перевод.

Вычисление максимального количества людей в лифте

#алгоритм #сложность

Дано список людей с именем и весом, максимальный вес который выдержит лифт. Вычислить
максимальное количество людей, которое может поместиться в лифт и вывести их список.

Не понимаю, как определить комбинацию людей которые могут быть. Ведь может быть разные
комбинации, 1, 2, 3 или 1, 2, 4, или 1, 3, 5, 6.
Хочу сначала узнать все возможные комбинации вместимых людей и потом выводить максимальное.
Но как узнать комбинации этих людей или как по другому решаются такие задачи

public class MaxLift {
public static void main(String[] args) {

    Man[] men = new Man[10];
    men[0] = new Man("0", 110);
    men[1] = new Man("1", 30);
    men[2] = new Man("2", 34);
    men[3] = new Man("3", 67);
    men[4] = new Man("4", 33);
    men[5] = new Man("5", 65);
    men[6] = new Man("6", 19);
    men[7] = new Man("7", 80);
    men[8] = new Man("8", 98);
    men[9] = new Man("9", 45);
    int liftMaxWeight = 200;

    TreeSet> set = new TreeSet<>();//add comparator
    for (int i = 0; i < men.length; i++) {
        List list  = new ArrayList<>();
        list.add()
    }

    //sout
}

private static class Man {
    String name;
    int weight;

    public Man(String name, int weight) {
        this.name = name;
        this.weight = weight;
    }
}


}
    

Ответы

Ответ 1

Так как в задании ничего не сказано про объём лифта, то решением является следующее.

Сортируем список людей начиная с самого малого веса, например:

20
25
27
30
40
50
60
75


И складываем подряд начиная с начала пока не получим максимальную массу.

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

Сложность алгоритма равна сложности сортировки. Но при желании можно ещё ускорить
не сортируя весь массив сразу, а сортируя только начало. Но это будет посложнее организовать,
так как придётся алгоритм сортировки писать вручную.


Ответ 2

Итак, ваш вопрос не как вычислить максимальное число людей в лифте, а "Хочу сначала
узнать все возможные комбинации и потом выводить максимальное. Но как узнать кобинации
этих людей".

Тогда можно просто перебирать все числа от 0 до 2N-1, где N - число людей. Дальше
каждое число в бинарном представлении - просто набор 0 и 1, соответствующих конкретным
людям, а все числа - все возможные варианты. Типа, для трех человек ABC:

0  000   никого :)
1  001   A
2  010   B
3  011   AB
4  100   С
5  101   AC
6  110   BC
7  111   ABC


Ответ 3

Чтобы найти сколько людей может в лифте поместиться, учитывая максимальный вес, можно
отсортировать веса людей и прибавлять от меньшего к большему весу до тех пор пока кумулятивный
вес меньше максимальной нагрузки лифта. На Питоне:

#!/usr/bin/env python
import itertools

weights = 110, 30, 34, 67, 33, 65, 19, 80, 98, 45
capacity = 200
for n, cumsum in enumerate(itertools.accumulate(sorted(weights))):
    if cumsum > capacity:  # no more
        print(n)
        break
else: # no break: all people can come in
    print(len(weights))


Ответ: 5 что совпадает с результатом более общего алгоритма для задачи о рюкзаке.



Weights:  Max weight:  

Примеры алгоритмов с логарифмической сложностью (основание отличное от 2)

#сложность

Допустим, говорят, что алгоритм имеет сложность O(log(N)). Всегда ли эта запись означает,
что логарифм берется по основанию 2? Понимаю, что обычно людей интересует поведение
функции, а не конкретные числа, но все же интересно, есть ли конкретные распространенные
алгоритмы, которые оцениваются логарифмом с другим основанием?
    

Ответы

Ответ 1

Ну это просто. Асимптотическая оценка сложности алгоритма O(N) не принимает во внимание
константу перед множителем, тк при больших N она становится несущественной, следовательно
O(N) = C1 * log(N) + C2 записывается как O(N) = log(N)

Известно также, что логарифм с любым основанием можно представить как логарифм по
основанию 2 умноженный на множетель-константу, который по описанной выше причине просто
не учитывается в оценке сложности O(N)


Ответ 2

При учете асимптотической сложности константы не учитываются. Основание логарифма
в данном случае не имеет значение. Т.к. логарифм можно привести к любому основанию,
пользуясь свойством   . 

Соответственно, если у нас есть обозначение O(логарифм n по основанию a), где a -
это какая то константа, это выражение упрощается до O(логарифм n по основанию с разделить
на логарифм a по основанию c), где c - это какая то константа. Получаем, что логарифм,
на который делят, можно не учитывать в нотации O, т.к. он от n не зависит, и является
константой.

Как посчитать сложность алгоритма?

#java #алгоритм #сложность

Исходные данные: файл, с одной единственной колонкой, в которой находятся числа от
0 до Integer.MAX_INT.

Нужно написать алгоритм, который будет подсчитывать количество повторений цифр в
этом файле.



Будем считать, что у нас бесконечное количество памяти. Напишем такой метод, а по
завершению просто распечатаем entries у этой коллекции: 

final Map map = new HashMap<>();
//----

public void add(Integer digit) {
    Integer quantity = map.get(digit);

    if (quantity == null) {
        map.put(digit, 1);
    } else {
        map.put(digit, ++quantity);
    }
}


Вопрос №1: Правильно ли я понимаю, что алгоритмическая сложность данного метода будет
O(1)? Т.к. внутри используется HashMap со сложностью поиска и добавления O(1).

Вопрос №2: Общая сложность системы будет равна O(n) ? 



А теперь заменим HashMap на TreeMap:

Вопрос №3: Сложность метода будет равна O(log(n)) ?

Вопрос №4: Сложность всей системы будет равен O(n) ? Т.к. он сложится из O(n) + O(log(n))
-> O(n) т.к. она растет быстрее чем логарифм. 
    

Ответы

Ответ 1

Вопрос №1: Правильно ли я понимаю, что алгоритмическая сложность данного метода будет
O(1)? Т.к. внутри используется HashMap со сложностью поиска и добавления O(1).


Да, с оговоркой про то, что вставка/поиск в хеше на неудачных данных может деградировать
до O(n),

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

Кроме того при обычной реализации динамически расширяемой хеш-таблицы map.put может
потребовать перестроения индекса хеша, сложность которого также O(n), но этого можно
избежать заранее выделив под таблицу достаточный объём данных.


  Вопрос №2: Общая сложность системы будет равна O(n) ?


Да, с аналогичной оговоркой, в худшем случае время составит O(n²).

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




  А теперь заменим HashMap на TreeMap:
  
  Вопрос №3: Сложность метода будет равна O(log(n)) ?


Да


  Вопрос №4: Сложность всей системы будет равен O(n) ? Т.к. он сложится из O(n) +
O(log(n)) -> O(n) т.к. она растет быстрее чем логарифм. 


Нет, здесь не верно: нужно N раз сделать операцию сложностью O(log(n)), где n в среднем
равно N/2. т.е. сложность будет O(N*log(N)).


Ответ 2

Да, все правильно. Перебор коллекции это всегда O(N), потому выполнение метода add
и печать всех элементов это O(N). В первом случае сложность функции add - O(1) в среднем(а
в худшем O(N), потому что в хеш-таблице могут быть коллизии), а во втором - O(log N)
в худшем случае потому что TreeMap это сбалансированное бинарное дерево поиска.

UPD К сожалению слегка ошибся, забыл что во втором случае мы N раз добавляем за логарифм
потому сложность O(N log N)


Ответ 3

"Нужно написать алгоритм, который будет подсчитывать количество повторений цифр в
этом файле."

Скажите на милость, зачем вам вообще какие-то HashMap, если вас интересуют цифры?
Массив из 10 целых, и вперед, чтение по одному символу, если цифра - увеличивать соответствующий
элемент массива. Все. Чистое O(размер файла).

Вы верно переписали задание? Просто в условии у вас одно задача, а решаете вы совсем
другую.

Оптимизация операций для двоичного индексированного дерева (дерево Фенвика)

#алгоритм #любой_язык #дерево #структуры_данных #сложность

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


Получение значений (выгрузка во внешний массив) префиксных сумм для
элементов из непрерывного диапазона от i до i + k.
Обнуление (или, скажем, заполнение константой) элементов из непрерывного
диапазона от i до i + k с корректным пересчетом всех затрагиваемых сумм.


Важно: Для обоих операций среднее значение k много меньше n (количества элементов
в дереве).

На данный момент реализованы эти операции тупо и просто:


В цикле (отдельно!) для каждого элемента из диапазона выполняется нахождение его
значения (стандартная операция для дерева Фенвика). Итого: сложность операции составляет
O(k*log(n)) для k элементов.
В цикле (отдельно!) для каждого элемента выполняется нахождение его значения, после
чего выполняется его инкремент на число обратное его текущему значению (для сброса
в ноль). Сложность, опять же, равна O(k*log(n)).


Я задумался над структурой деревьев и этими операциями. И мне кажется, обе они могут
быть реализованы с меньшей сложностью. Ведь log(n) это глубина прохода от корня до
произвольного элемента, а в этих операциях выполняется обход группы последовательно
расположенных элементов. Из этого факта возможно извлечь пользу, так как ближайший
общий узел дерева в лучшем случае лежит на глубине log(k) от любого из конечных узлов
в непрерывном диапазоне длинной k. Значит для обхода всего диапазона можно спуститься
от корня за log(n), после чего подниматься и спускаться от одного соседнего элемента
к другому за log(k). Итого: сложность алгоритма должна составить O(log(n) + k*log(k))
(что намного лучше текущего варианта). Это для лучшего случая. Но и средняя оценка
должна быть близка к этому, так как худший случай O(k*log(n)) маловероятен при k ≪ n.

Сейчас я залип над реализаций алгоритмов для этих двух операций. Пока что мне не
совсем понятно как перейти от элемента i к элементу i+1, не возвращаясь к корню. По
идее надо подниматься до ближайшего общего узла и спускаться обратно к следующему элементу,
по дороге подсчитывая суммы, необходимые для получения значения следующего элемента.
А для операции (2), видимо, следует на этом же проходе одновременно корректировать
значения промежуточных узлов как при выполнении стандартного инкремента (если это вообще
возможно сделать одновременно).

Это все общие соображения для бинарных деревьев. Как это должно реализовываться конкретно
для дерева Фенвика я пока не представляю.

Буду благодарен за помощь с конкретными алгоритмами на псевдокоде или любом императивном
языке.

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

Ответы

Ответ 1

Да, можно попробовать ускорить эти операции. Приведу для начала свою реализацию: 

int next2n(int x) {
    // only 32bit
    x = x - 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x+1;
}
class BIT_plus {
    std::vector in;
    std::vector num;
    int n;
     public:
    BIT_plus(int n) {
        init(n);
    }

    BIT_plus(const std::vector& list) {
        init(list);
    }

    void init(const std::vector& list) {
        init(list.size());
        for(auto i=0u; i < list.size(); ++i) {
            inc(i, list[i]);
        }    
    }

    std::vector sum_dip(int start, int len) {
        int summ = sum(start);
        std::vector res;
        for(int i=start; i < start + len; i++) {
            res.push_back(summ);
            summ += num[i+1];
        }
        return res;
    }

    void init(int n) {
        in.assign(n, 0);
        num.assign(n, 0);
        this->n = n;
    }

    int size() {
        return n; 
    }

    void inc (int i, int delta) {
        num[i] += delta;

        for (; i < n; i = (i | (i+1)))
            in[i] += delta;
    }

    int sum (int r) const {
        int result = 0;
        for (; r >= 0; r = (r & (r+1)) - 1)
            result += in[r];
        return result;
    }

    int sum (int l, int r) const{
        return sum (r) - sum (l-1);
    }

    void fill_const(int start, int len, int val) {
        int n2n = next2n(start + len + 1)-1;
        int sumdelta = 0;
        for(int i = start; i < start + len; i++) {
            int delta = val - num[i];
            sumdelta += delta;
            for(int j = i; j < n2n; j = (j|(j+1))) {
                in[j] += delta;
            }
            num[i] = val;
        }
        for(int i = n2n; i < n; i = (i|(i+1))) {
            in[i] += sumdelta;
        }
    }

    auto get_num() const {
        return num;
    }
    auto get_in() const {
        return in;
    }
};


Она немножко раздута лишними методами, но всё самое важное в ней есть. (За некоторую
основу взял реализацию отсюда). В ней по сравнению с обычной реализацией есть два новых
метода: fill_const (заполняет определенным числом диапазон исходной последовательности)
и sum_range (возвращает префиксные суммы элементов из диапазона).



Основная идея реализации довольно проста. Она заключается в том, что помимо непосредственно
массива для дерева Фенвика(in) мы храним и сами исходные элементы (num).
1. Тогда нахождение всех префиксных сумм из диапазона [i, i+k] происходит так: сначала
мы находим префиксную сумму для i-го элемента. Это происходит как и в обычной реализации.
Сложность вычисления будет O(log(n)). А дальше, чтобы найти sum(i+1) прибавить число
num[i+1]. И действительно если sum(i) -- сумма первых i элементов, то 
sum(i) + num[i+1] -- сумма первых i+1 элемента.
2. Вторая часть с заполнением константой чуть сложнее. Сначала поймём, какие элементы
нам нужно изменить в исходном массиве in. Если мы
 меняем элемент с индексом i, то сначала мы должны сменить элемент с индексом i,
потом f(i), f(f(i)), где f(i) = i|(i+1) ( | --
 побитовое или).
Заметим, что если в какой-то момент мы попали в 2k-1, то дальше мы также будем попадать
в 2i-1. Более того, если мы начинаем из некого числа i, то в следующее за ним число
вида 2k-1 мы2 не пропустим (иначе как мы получим единицу в следующем разряде, а функция
у нас монотонно возрастающая). 
Воспользуемся этим так: от числа j из [i, i+k) будем изменять ячейки (по стандартным
правилам. Прибавляя к ним delta) пока номер ячейки, которую мы меняем будет меньше,
чем следующее за i+k число вида 2k-1 (next2n(i+k)). Дальше же индексы массива, который
мы будем менять для всех j совпадут. И менять мы их будем на сумарную величину изменений
всех ячеек.

Вероятно, второй алгоритм можно несколько оптимизировать (сейчас он работает, кажется,
за O(k*log(i)+log(N)), что асимптотически не быстрее (i может быть порядка n), но быстрее
практически особенно при маленькиx i), но уже в такой его реализации он будет работать
быстрее, чем независимое изменение для каждой переменной.


Ответ 2

Операция выгрузки ответов во внешний массив делается за O(k + log n) следующим образом:


Отдельно храним исходный массив
Выгружаем за O(log n) сумму до первого элемента (i).
За O(1) прибавляем к ней элемент i+1, получаем сумму до элемента i+1.
Аналогично считаем суммы до всех элементов до i+k, итого O(k) операций.


С изменением сложнее - дерево Фенвика такую операцию так просто не поддерживает.
Однако вам может помочь дерево отрезков с групповым изменением - оно весьма популярно
в спортивном программировании. По этому поводу есть, например, руководство на e-maxx,
но никаким разумным стандартам читаемости и поддерживаемости кода оно не удовлетворит,
поэтому надо вникать и писать свою реализацию (возможно, есть библиотечная, но я не
изучал).

Дерево отрезков позволит сделать подсчёт суммы и массовое присваивание на любом отрезке
за O(log n) (независимо от k), а выгрузку операций можно либо сделать за O(k * log
n) "в лоб", либо за O(k + log n) примерно той же оптимизацией, что и с Фенвиком - сначала
считаем сумму до элемента i, а далее по одному находим значения следующих элементов.
Это можно делать массово, и там получится O(k) операций (придётся полностью обойти
несколько поддеревьев суммарного размера O(k)).


Ответ 3

Алгоритмы с использованием массива исходных данных (из которых строилось дерево)
будут, конечно, работать быстрее. Так что, если проект позволяет хранить копию исходных
данных параллельно с деревом Фенвика, рекомендую обратиться в первую очередь к ответам
других участников.

Мне же было интересно повозиться только с самим деревом Фенвика. Поэтому мои решения
не столь быстры, зато позволяют не хранить копию исходных данных.

Пункт 1 - получение значений (выгрузка во внешний массив) префиксных сумм для элементов
из непрерывного диапазона от i до (i+k)

Перейти от префиксной суммы i-го элемента к префиксной сумме (i+1)-го на самом деле
несложно.
У меня получился следующий алгоритм:
1) собираем частичные суммы, составляющие i-й элемент, кладём их в структуру данных
"стек", в порядке их индексов в дереве от наименьших к наибольшим;
   в целях оптимизации можно хранить в стеке не сами частичные суммы а нарастающий
итог по ним;
   вершина стека при этом будет хранить значение i-й префиксной суммы (возвращаем
её в ответ);
например, при i = 10, стек будет таким:
   stack[0] = tree_item[7]
   stack[1] = tree_item[7] + tree_item[9]
   stack[2] = tree_item[7] + tree_item[9] + tree_item[10]  // вершина стека, равная
10-му префиксу
   кстати, максимальный размер этого стека совсем невелик - log2(max_size), т.е.
когда количество исходных элементов описывается 32-разрядным числом, размер данного
стека будет всего 32 элемента;
2) рассматриваем двоичную запись числа (i+1), записывая биты слева направо от старших
к младшим;
   если двоичная запись заканчивается нулём, переходим к следующему шагу;
   если двоичная запись заканчивается некоторой непрерывной последовательностью единиц,
то подсчитываем количество этих единиц, и удаляем с вершины стека столько элементов,
сколько обнаружили завершающих единиц;
например, при i = 10, имеем:
   (i+1) = 11 (десятичная запись) = 0001011 (двоичная запись);
   двоичная запись числа заканчивается группой из 2-х единиц;
   следовательно, снимаем со стека 2 элемента, и содержимое стека становится таким:
   stack[0] = tree_item[7]
3) добавляем в стек (i+1)-й элемент дерева;
   при этом вершина стека станет содержать значение (i+1)-й префиксной суммы (возвращаем
её в ответ);
например, при i = 10, имеем:
   stack[0] = tree_item[7]
   stack[1] = tree_item[7] + tree_item[11]  // вершина стека, равная 11-му префиксу
4) повторяем шаги 2-3 для индексов (i+2),(i+3),...(i+k).

для большей ясности выпишу ещё несколько шагов:
   (i+2), двоичная запись 0001100; из стека ничего не удаляется;
   stack[0] = tree_item[7]
   stack[1] = tree_item[7] + tree_item[11]
   stack[2] = tree_item[7] + tree_item[11] + tree_item[12]  // 12-й префикс
   (i+3), двоичная запись 0001101; из стека удаляется только 1 элемент;
   stack[0] = tree_item[7]
   stack[1] = tree_item[7] + tree_item[11]
   stack[2] = tree_item[7] + tree_item[11] + tree_item[13]  // 13-й префикс
   (i+4), двоичная запись 0001110; из стека ничего не удаляется;
   stack[0] = tree_item[7]
   stack[1] = tree_item[7] + tree_item[11]
   stack[2] = tree_item[7] + tree_item[11] + tree_item[13]
   stack[3] = tree_item[7] + tree_item[11] + tree_item[13] + tree_item[14]  // 14-й
префикс
   ...
все эти операции со стеком очень легко понять если смотреть на картинку, изображающую
дерево Фенвика в 2-мерном виде, примерно как здесь

По части владения Big-O-notation у меня не очень, поэтому не могу точно определить
сложность данного алгоритма. Могу только сказать, что это точно будет намного лучше,
чем O(k*log(i)), когда i достаточно велико.

Пункт 2 - заполнение константным значением элементов из непрерывного диапазона от
i до (i+k) с корректным пересчетом всех затрагиваемых сумм

Здесь у меня получилось очень похоже на то, что описано в ответе участника retorta,
поэтому не буду зря дублировать.
Упомяну только о том, что тут приходилось дополнительно вычислять исходные значения.
value[i] = prefix(i) - prefix(i-1)
Тривиальная реализация требует 2*k обращений к функции вычисления префиксной суммы,
и это легко оптимизировать до (k+1) обращений.
Однако, можно зайти и с другой стороны: неплохо оптимизируется функция, вычисляющая
i-е значение исходного массива, если основываться на том, что каждый чётный элемент
дерева есть значение исходное, а из нечётных каждый второй - равен сумме i-го и (i-1)-го
исходных значений, и т.д...
В общем же случае - опять "выстреливает" подсчет количества единичных битов в младших
разрядах числа, как и по пункту 1 :)

Реализация
Текста получилось уже и так довольно много, поэтом код я решил вынести на github,
надеюсь это не запрещается :)
Закодил в итоге на C++ в MS Visual Studio Community 2015.
В коде отсутствуют некоторые проверки, зато есть простенькие тесты на валидность
и производительность кода.
Отдельно хочу напомнить, что результаты замеров сильно различаются в Debug- и Release-конфигурациях,
в последней выигрыш обычно меньше.
Ссылка на код

Почему для вычисления сложности алгоритмов используется log N вместо lb N?

#алгоритм #математика #сложность

Во всех источниках сложность алгоритмов обозначается как log N (без указания основания).
При этом имеется в виду логарифм по основанию 2.

Но для такого логарифма есть свое обозначение lb. Причем это обозначение стандартизировано
ISO 31-11 и наверное было бы логичнее и правильнее пользоваться именно им, но этого
по какой-то причине не просходит, почему?

UPD: у меня нет никакого математического образования и все, что я знаю о логарифмах,
что это действие обратное возведению в степень.

Возьмем конкретный пример - бинарный поиск. Везде описывают его сложность как log
N. При этом под log N, как мне кажется, все таки подразумевается логарифм N по основанию
именно 2, т.к. количество операций составляет именно логарифм N по основанию 2, т.е.
в какую степень надо возвести именно 2 (а не 10 и не 100), чтобы получить N. Поэтому,
если честно, я не понимаю ответов типа "потому что постоянные коэффициенты в обозначении
O(n) не имеют значения" или "так как запись с большим O на константы не реагирует -
неважно, какой именно логарифм использовать..." и буду признателен за более развернутый
ответ, написанный не для математиков. Разве правило, что "константы в О-большом не
имеют значения", относится к основанию логарифма? Разве для бинарного поиска не имеет
никакой разницы как записать его сложность - логарифмом по основанию 2 или по основанию 100?

Если под log N для бинарного поиска подразумевается именно логарифм по основанию
2, то почему бы его не записать как lb N, раз уж для двоичного логарифма есть свое
обозначение, вместо того, чтобы записывать вообще без указания основания?

UPD 2: я понимаю что "O(N) - это ни в коем случае не количество сравнений, это оценка
времени работы алгоритма, максимально отвязанная от деталей реализации и машины." 

Но вот этого: "А так как запись с большим O на константы не реагирует - неважно,
какой именно логарифм использовать..." я не понимаю. Почему не важно какой логарифм
использовать? Вот графики трех логарифмов - двоичного, натурального и по основанию 0,5:



Возьмем все тот же бинарный поиск. Разве мы можем заменить в его сложности основание
у логарифма с два на десять? А с два на 0,5? Мне кажется, не можем. Т.е. мы не можем
подставить в выражении log N произвольное основание потому что зависимость будет совершенно
другая - это хорошо видно на графике. Т.е. какой именно логарифм использовать важно.
Или я не прав? 
    

Ответы

Ответ 1

Поскольку все логарифмы одинаковы с точностью до константы :)



А так как запись с большим O на константы не реагирует - неважно, какой именно логарифм
использовать...

Update на ваше обновление вопроса.

Смысл не в конкретном количестве сравнений, а в том, как растет это количество (а
значит, и время работы) с ростом N. Это ни в коем случае не конкретное количество тех
или иных операций! То, что некоторый алгоритм имеет сложность O(g(N)) всего лишь означает,
что если мы путем экспериментов будем строить некую функцию зависимости времени работы
алгоритма от N и получим некую f(N), то сможем найти некоторые такие константные c
и N0, что для всех N>=N0 будет выполняться неравенство 0 <= f(N) <= cg(N). Это - определение
записи с большим О.

Еще раз - O(N) - это ни в коем случае не количество сравнений, это оценка времени
работы алгоритма, максимально отвязанная от деталей реализации и машины.

Update2

Я реализую алгоритм бинарного поиска и при этом ужасно туплю, так что вместо одного
сравнения я делаю их 20. Вы делаете их ровно столько, сколько нужно. Но и ваша, и моя
реализации будут работать время O(log N) - пусть моя и будет работать в 100 раз медленнее
вашей. Потому что и моя, и ваша реализации при возрастании N в 100 раз будут работать
дольше на некоторое время - пусть и у каждого свое, скажем, у вас на минуту, у меня
- на час. Главное, что вид зависимости будет одинаков - при увеличении в сколько-то
раз рост будет на сколько-то.

И, кстати, у вас зависимости log2x и ln x как раз одинаковы - стоит только немного
изменить масштаб по оси y. Что до логарифма по основанию, меньшему 1 - ну, как говорится,
не стоит утрировать. Но и тут - достаточно взять его по модулю или отрицательную константу :)

А вообще, хватит уже этой переписки - если вас интересует, что такое большое O -
то это уже совсем отдельный вопрос...

Кстати, вот несколько ссылок отсюда:

Введение в анализ сложности алгоритмов (часть 1)

Введение в анализ сложности алгоритмов (часть 2)

Введение в анализ сложности алгоритмов (часть 3)

Введение в анализ сложности алгоритмов (часть 4)


Ответ 2

Мне кажется, я нашел ответ на свой изначальный вопрос: 

"Во всех источниках сложность алгоритмов обозначается как log N (без указания основания).
При этом имеется в виду логарифм по основанию 2.
Но для такого логарифма есть свое обозначение lb. Причем это обозначение стандартизировано
ISO 31-11 и наверное было бы логичнее и правильнее пользоваться именно им, но этого
по какой-то причине не просходит, почему?"

вот здесь:
https://en.wikipedia.org/wiki/Logarithm#Particular_bases

т.е. например, в информатике log N используется вместо lb N или log N по конкретному
основанию, потому что основание логарифма понятно из контекста.

Возможно, основание логарифма вообще значения не имеет, когда речь идет об О-большое,
как ответил @Harry. Но, если честно, моих математических знаний на данный момент не
хватает, чтобы дать этому утверждению оценку. Поэтому я предпочту пока более общую
формулировку про то, что "основание определено контекстом"



UPD: Набрел в одной книг по алгоритмам (как раз в разделе бинарного поиска) на фразу:
"Is it log base 2, log base 10, or the natural log?
In the above example, log base 2 applies. However, since Big O notation only concerns
itself with the shape of the performance the actual base doesn't matter." Так что,
да, похоже основание логарифма не важно )

Существуют ли реальные алгоритмы со сложностью O(1/n)?

Существуют ли реальные алгоритмы со сложностью O(1/n)? В голову лезет только ерунда по типу:

function test(n) {
  for (i=1; i<100000/n; i++) {
    dosomething();
  }
}

    

Ответы

Ответ 1

Их даже в теории не существует. Потому что это ограничение сверху.

O(C + 1/n) = O(C) = O(1)


Где C - некоторая константа, отличная от 0.

А 0 она не может быть равна, поскольку у нас в любом случае есть накладные расходы хотя бы на получение самого n и какое-то его использование.

Потому что если мы не используем n вообще, то сложность, очевидно, от него не зависи
и не может быть O(1/n). А если используем, то мы хоть раз к нему обратимся и константа будет ненулевой.



Альтернативное обоснование: представим, что такой алгоритм есть, но тогда при удвоени
n время его исполнения уменьшается вдвое и при достаточно большом n должно будет стать менее одной процессорной инструкции, что невозможно.



Даже в коде из вопроса


for (i=1; i<100000/n; i++) {



что произойдёт, когда n превысит 100000?

У нас будет ровно 4 операции: присваивание, деление, сравнение и выход из функции. Это O(1) - оно уже неспособно уменьшиться с ростом n.


Ответ 2

Нет, не существует.

Сначала вспомним, что такое асимптота:

Пусть у нас есть некая кривая y = A(x). Тогда асимптота y = B(x) — это такая кривая, к которой A как бы «прижимается» при движении в бесконечность вдоль оси x.

Графически это выглядит так:



Источник: https://en.wikipedia.org/wiki/File:1-over-x-plus-x.svg

В данном примере прямая y = x является асимптотой для y = 1 / x + x, так как пр
достаточно больших x обе линии практически сливаются.

Асимптотатическая сложность ведёт себя аналогичным образом, только вместо графиков у нас зависимость вычислительной сложности от количества элементов.

Соответственно, чтобы утверждать, что алгоритм имеет сложность O(1 / N), надо, чтоб
график сложности алгоритма совпадал с графиком 1 / n при очень больших n. Но в этом случае 1 / n вырождается в константу ноль. А раз у нас константа, значит и алгоритм имеет константную сложность, обозначаемую как O(1).


Ответ 3

А вообще, есть интересный случай. В большинстве случаев говоря об асимптотике м
предполагаем возрастание аргумента. Но, строго говоря, это может быть не так. Например, если мы знаем, что область определения некоторой функции ограничена. Возьмём и реализуем деление int(1/x) через вычитание:



function f(x) {
  for (var i=0, v=1; v>0; ++i, v-=x);
  return i;
}

console.log(f(1));
console.log(f(.5));
console.log(f(.25));
console.log(f(.125));
console.log(f(.0625));
console.log(f(.0000001));




В принципе можно сказать, что у этой функции асимптотика O(1/x), т. е. при маленьки
значениях x она будет работать очень медленно (кстати, ещё и неточно из-за накопления погрешноти). Разумеется, в случае с целым аргументом такой вариант будет невозможен.

Амортизированная константа

Может кто-нибудь объяснить, что означает амортизированная сложность алгоритма, в частности, амортизированная константа? Это когда для массива операция выполняется не каждый вызов, а только один раз?

Ответ

Ну вот смотрите. Берем динамическим массив. Сначала из одного элемента.
Добавляем еще один. Удваиваем массив. Итого - одно выделение, один перенос (первого элемента).
Еще добавление - массив становится равен 4 элементам. Выделений - 2. переносов - 3 (теперь переносим 2 элемента, + 1 ранее). Добавление четвертого элемента не требует ни выделения, ни переноса.
Еще добавление. Массив увеличивается до 8 элементов. Теперь в массиве 8 элементов, 3 выделения памяти, 7 переносов элементов. Элементы с 6 по 8 не требуют ни выделения, ни переноса...
...
Теперь у нас 2n элементов, n выделений памяти, 2n-1 переноса элементов.
Т.е. в среднем каждый элемент пришлось переносить 1-2-n раз, при больших n - 1 раз.
Константа? Да. При том, что первый элемент переносился log2n раз.
А вот в среднем, т.е. амортизированно - константа.
Так более-менее понятно?

Сложность алгоритма, содержащего рандомную операцию

Для всякого ли алгоритма можно оценить сложность при помощи О нотации?
Допустим, я имею массив чисел и хочу вытащить оттуда любое, условно, четное. Но перебирать их буду не по-порядку, а рандомно, в бесконечном цикле, пока не найду нужное. Конечно, это очень кривой подход (в плане доступа к кэшам, например), но можно ли оценить его алгоритмическую сложность?

Ответ

Да, можно. Следует оценивать с учётом вероятности.
Например, сложность bogosort оценивается как
я имею массив чисел и хочу вытащить оттуда любое, условно, четное. Но перебирать их буду не по-порядку, а рандомно, в бесконечном цикле, пока не найду нужное.
Если в массиве около половины чисел чётные, то O(1). Если только одно число чётное, то O(n) с жирненькой константой. Если ни одного, то алгоритм вообще не завершится.
Если рассматривать случайный (равномерный) массив, то, вероятно, будет сводиться к O(1) - как доступ по ключу хэш-таблицы.
PS: Провёл эксперимент для случая с единственным искомым числом (результат смотреть в реальной консоли, открытой до запуска сниппета; при запуске браузер может зависнуть на несколько секунд):
function go(n) { while (Math.random() * n | 0); } var res = []; function check(n) { var t = performance.now(); go(1< x+y) } } console.table(res.map(stat));

При удвоении длины время увеличивается вдвое, т. е. действительно O(n).

P-класс задач и NP- класс задач

Объясните пожалуйста как можно подробнее , что такое Р задачи , NP (полные , сложные ..) задачи . А то почитав так и не понял. Спасибо заранее

Ответ

Смотрите, речь идёт об асимптотической сложности задач. Здесь рассматриваются только задачи, которые имеют простой однозначный ответ: «да» или «нет». Например, «есть ли подстрока "XYZ" в данной строке?». Задачи типа «найдите все перестановки данного набора чисел» как P/NP-проблемы не рассматриваются, так как ответ тут не да/нет. Алгоритмы часто параметризуются размерами входных данных. Время пробега алгоритма в общем случае тем больше, чем больше данных ему приходится обрабатывать. Обозначим n1, n2, ... — параметры, описывающие размеры входных данных, t(n1, n2, ...) — максимальное время работы алгоритма на данных такой длины. Если известно, что t(n1, n2, ...) ограничено сверху многочленом от переменных n1, n2, ..., задача называется решаемой за полиномиальное время. Класс таких задач и обозначается как P, они считаются вычислительно несложными. Теперь, что же такое NP-проблема? Представьте себе, что у вас есть алгоритм с несколькими ветвлениями (if-ами, циклами), который последовательно тестирует решения, и как только найдёт подходящее, сразу заканчивает алгоритм с криками «ура, нашёл!» Например, если мы ищем, есть ли символ 'X' в данной строке, мы можем поочерёдно в цикле проверять, совпадает ли первый символ с X, затем второй, затем третий, и как только нашли совпадение, заканчиваем работу. Так вот, представьте себе теперь такую машину, которая магическим образом сразу переходит к нужной итерации цикла: для поиска символа X в строке "ABCXYZ" она сразу проверяет в 4-ой позиции, то есть там, где надо! Такая магическая машина называется недетерминированной машиной (по историческим причинам) и, понятно, не существует в природе. Так вот, проблема называется NP-проблемой, если она решается за полиномиальное время на этой самой читерской недетерминированной машине. Понятно, что всякая P-проблема есть NP-проблема: если уж мы на нормальной машине решим её за полиномиальное время, то на читерской тем более! Возникает вопрос: а нужно ли читерство? Может быть, всякая проблема, которая решается на недетерминированной машине за полиномиальное время, может быть решена и на нормальной тоже за полиномиальное время? Это и есть знаменитая P/NP-гипотеза: предполагают, что есть проблемы, которые без недетерминированной машины за полиномиальное время не решить. Но никто пока не смог это строго математически обосновать. Проблема тут вот в чём: если мы не умеем решать какую-то задачу за полиномиальное время, значит ли это, что она в принципе за полиномиальное время не решается, или мы просто недостаточно умны и изобретательны?

Вычисление максимального количества людей в лифте

Дано список людей с именем и весом, максимальный вес который выдержит лифт. Вычислить максимальное количество людей, которое может поместиться в лифт и вывести их список.
Не понимаю, как определить комбинацию людей которые могут быть. Ведь может быть разные комбинации, 1, 2, 3 или 1, 2, 4, или 1, 3, 5, 6 Хочу сначала узнать все возможные комбинации вместимых людей и потом выводить максимальное. Но как узнать комбинации этих людей или как по другому решаются такие задачи
public class MaxLift { public static void main(String[] args) {
Man[] men = new Man[10]; men[0] = new Man("0", 110); men[1] = new Man("1", 30); men[2] = new Man("2", 34); men[3] = new Man("3", 67); men[4] = new Man("4", 33); men[5] = new Man("5", 65); men[6] = new Man("6", 19); men[7] = new Man("7", 80); men[8] = new Man("8", 98); men[9] = new Man("9", 45); int liftMaxWeight = 200;
TreeSet> set = new TreeSet<>();//add comparator for (int i = 0; i < men.length; i++) { List list = new ArrayList<>(); list.add() }
//sout }
private static class Man { String name; int weight;
public Man(String name, int weight) { this.name = name; this.weight = weight; } }
}

Ответ

Так как в задании ничего не сказано про объём лифта, то решением является следующее.
Сортируем список людей начиная с самого малого веса, например:
20 25 27 30 40 50 60 75
И складываем подряд начиная с начала пока не получим максимальную массу.
Очевидно что максимальное количество людей меньше заданного веса это люди с минимальным весом, так как если заменить одного из этого минимального набора на другого человека вес прибавится.
Сложность алгоритма равна сложности сортировки. Но при желании можно ещё ускорить не сортируя весь массив сразу, а сортируя только начало. Но это будет посложнее организовать, так как придётся алгоритм сортировки писать вручную.

Как посчитать сложность алгоритма?

Исходные данные: файл, с одной единственной колонкой, в которой находятся числа от 0 до Integer.MAX_INT.
Нужно написать алгоритм, который будет подсчитывать количество повторений цифр в этом файле.

Будем считать, что у нас бесконечное количество памяти. Напишем такой метод, а по завершению просто распечатаем entries у этой коллекции:
final Map map = new HashMap<>(); //----
public void add(Integer digit) { Integer quantity = map.get(digit);
if (quantity == null) { map.put(digit, 1); } else { map.put(digit, ++quantity); } }
Вопрос №1: Правильно ли я понимаю, что алгоритмическая сложность данного метода будет O(1)? Т.к. внутри используется HashMap со сложностью поиска и добавления O(1).
Вопрос №2: Общая сложность системы будет равна O(n) ?

А теперь заменим HashMap на TreeMap
Вопрос №3: Сложность метода будет равна O(log(n)) ?
Вопрос №4: Сложность всей системы будет равен O(n) ? Т.к. он сложится из O(n) + O(log(n)) -> O(n) т.к. она растет быстрее чем логарифм.

Ответ

Вопрос №1: Правильно ли я понимаю, что алгоритмическая сложность данного метода будет O(1)? Т.к. внутри используется HashMap со сложностью поиска и добавления O(1).
Да, с оговоркой про то, что вставка/поиск в хеше на неудачных данных может деградировать до O(n)
Здесь стоит оговориться, что для хеша с адекватной хеш-функции, подходящем размере таблицы и при квазислучайных входных данных вероятность худшего случая пренебрежимо мала, но всегда существует такой набор данных, который этот случай даст. Зачастую его можно специально подобрать и даже использовать для DOS-атаки.
Кроме того при обычной реализации динамически расширяемой хеш-таблицы map.put может потребовать перестроения индекса хеша, сложность которого также O(n), но этого можно избежать заранее выделив под таблицу достаточный объём данных.
Вопрос №2: Общая сложность системы будет равна O(n) ?
Да, с аналогичной оговоркой, в худшем случае время составит O(n²)
В случае динамически расширяемой хеш таблицы в типовой реализации также необходимо увеличивать её размер и пересчитывать хеши порядка log(N) раз и время соответственно может ухудшиться до O(N*log(N)) в среднем случае, но этот эффект будет проявляться только для относительно больших N и зачастую его так или иначе можно нивелировать (выделяя заведомо больше памяти).

А теперь заменим HashMap на TreeMap: Вопрос №3: Сложность метода будет равна O(log(n)) ?
Да
Вопрос №4: Сложность всей системы будет равен O(n) ? Т.к. он сложится из O(n) + O(log(n)) -> O(n) т.к. она растет быстрее чем логарифм.
Нет, здесь не верно: нужно N раз сделать операцию сложностью O(log(n)), где n в среднем равно N/2. т.е. сложность будет O(N*log(N))

Существуют ли реальные алгоритмы со сложностью O(1/n)?

Существуют ли реальные алгоритмы со сложностью O(1/n)? В голову лезет только ерунда по типу:
function test(n) { for (i=1; i<100000/n; i++) { dosomething(); } }

Ответ

Их даже в теории не существует. Потому что это ограничение сверху.
O(C + 1/n) = O(C) = O(1)
Где C - некоторая константа, отличная от 0.
А 0 она не может быть равна, поскольку у нас в любом случае есть накладные расходы хотя бы на получение самого n и какое-то его использование.
Потому что если мы не используем n вообще, то сложность, очевидно, от него не зависит и не может быть O(1/n). А если используем, то мы хоть раз к нему обратимся и константа будет ненулевой.

Альтернативное обоснование: представим, что такой алгоритм есть, но тогда при удвоении n время его исполнения уменьшается вдвое и при достаточно большом n должно будет стать менее одной процессорной инструкции, что невозможно.

Даже в коде из вопроса
for (i=1; i<100000/n; i++) {
что произойдёт, когда n превысит 100000?
У нас будет ровно 4 операции: присваивание, деление, сравнение и выход из функции. Это O(1) - оно уже неспособно уменьшиться с ростом n

Существуют ли реальные алгоритмы со сложностью O(1/n)?

Существуют ли реальные алгоритмы со сложностью O(1/n)? В голову лезет только ерунда по типу:
function test(n) { for (i=1; i<100000/n; i++) { dosomething(); } }

Ответ

Их даже в теории не существует. Потому что это ограничение сверху.
O(C + 1/n) = O(C) = O(1)
Где C - некоторая константа, отличная от 0.
А 0 она не может быть равна, поскольку у нас в любом случае есть накладные расходы хотя бы на получение самого n и какое-то его использование.
Потому что если мы не используем n вообще, то сложность, очевидно, от него не зависит и не может быть O(1/n). А если используем, то мы хоть раз к нему обратимся и константа будет ненулевой.

Альтернативное обоснование: представим, что такой алгоритм есть, но тогда при удвоении n время его исполнения уменьшается вдвое и при достаточно большом n должно будет стать менее одной процессорной инструкции, что невозможно.

Даже в коде из вопроса
for (i=1; i<100000/n; i++) {
что произойдёт, когда n превысит 100000?
У нас будет ровно 4 операции: присваивание, деление, сравнение и выход из функции. Это O(1) - оно уже неспособно уменьшиться с ростом n