Производительность выполнения побитовых операций на битовых наборах
В C++, если я делаю логическое ИЛИ (или И) на двух наборах битов, например:
bitset<1000000> b1, b2;
//some stuff
b1 |= b2;
Это происходит за O(n) или O(1) раз? Зачем?
Кроме того, можно ли это сделать, используя массив bools за O(1) раз?
Благодарю.
3 ответа
Это должно произойти за время O(N), поскольку существует конечное число битов, которые могут быть обработаны в любой данный отрезок времени данной платформой процессора. Другими словами, чем больше битовый набор, тем больше времени займет каждая операция, и увеличение будет линейным по отношению к количеству битов в битовом наборе.
Вы также сталкиваетесь с той же проблемой, используя массив bool типы. В то время как каждая отдельная операция займет O(1) времени, общее количество времени для N объектов будет O(N).
Я думаю, что нужно прояснить, что Big O является границей - асимптотической границей (минимальное требуемое время не может быть меньше, чем Big O в f (x)), и, размышляя об этом, оно утверждает порядок величины скорости вычислений. Итак, если вы думаете о том, как работает массив - если вы можете сказать, что я могу сделать эту операцию все в одном вычислении или около того, или есть известное количество, которое очень мало и намного меньше, чем N, то это является постоянным. Если вам нужно выполнить итерацию каким-либо образом (в этом случае вы увидите, что все биты должны быть проверены, и нет сокращения для побитового ИЛИ - поэтому необходимо вычислить N битов, и, следовательно, это O (n На самом деле это более узкая граница, но мы имеем дело только с Big O]. Сам массив хранит в себе N-бит.
На самом деле, немногие вещи действительно являются O(1) (просмотр индекса по известному адресу с использованием указателя может быть O(1) (если вы уже знаете, что ищете). Но, если у вас есть M вещей, которые нужно искать в постоянное время, то это O(M) * O(1) = O(M).
Это функция современного компьютера - так как большинство вещей обрабатываются последовательно. (многоядерный помогает, но еще не приблизился к влиянию на большие обозначения O). Конечно, есть способность компьютера обрабатывать слова параллельно, но даже это просто постоянное вычитание. O(n) / O(64) - все еще O (n).
Невозможно выполнить логическую операцию (например, ИЛИ или И) для произвольных массивов флагов в единицу времени. Настоящий анализ Big-Oh имеет дело со временем выполнения, так как размер данных стремится к бесконечности, и Core i7 никогда не собирается делать ИЛИ вместе миллиард бит, в то же время, что и ИЛИ вместе два бита.