#c #arrays #time-complexity #big-o
Вопрос:
Я пытаюсь лучше понять временную и пространственную сложность различных решений. Эта программа находит левую и правую сумму массива. Я почти уверен, что это O(n) O(n). Кто-нибудь может подтвердить?
vector<int> arrayOfProducts(vector<int> array) {
vector<int> vec;
for (int i = 0; i < array.size(); i ) {
int leftidx = i - 1, rightidx = i 1;
int leftSum = 1, rightSum = 1, totalSum = 1;
if (leftidx >= 0){
while (leftidx >= 0){
leftSum *= array[leftidx];
leftidx--;
}
}
if (rightidx < array.size()) {
while (rightidx < array.size()) {
rightSum *= array[rightidx];
rightidx ;
}
}
totalSum = leftSum * rightSum;
vec.push_back(totalSum);
}
return vec;
}
Комментарии:
1. Можете ли вы дать более подробную информацию о том, почему вы почти уверены, что это O(n) O(n)? На первый взгляд я вижу вложенные циклы, я думаю, O(n^2). Не имеет отношения к сложности времени, но вы вычисляете сумму, многократно вызывая
*=
?2. Я почти уверен, что это можно сделать в O(N), но Натан прав, что этот код этого не делает.
3. Если быть точным, то каждый вывод, по-видимому, является произведением всех элементов массива, кроме того, который находится в позиции
i
. Это можно было бы вычислить, сначала найдя произведение всех элементов массива в O(N), а затем разделив его на каждый отдельный элемент.4. Если размер вектора равен
N
, то сначалаwhile
выполняется 0 1 2 … N-1 раз, а второй N-1 N-2 … 0 раз. Поскольку оба они равны O(N^2), сложность составляет O(2*N^2), что равно O(N^2)
Ответ №1:
Вам может быть интересно, что Google Benchmark может оценить сложность алгоритмов для вас.
Вы можете скачать библиотеку тестов здесь и пример теста сложности здесь. Создание библиотеки должно быть простым, если вы прочтете инструкции здесь. Вам понадобится git cmake. Если вы не хотите его устанавливать, вы можете воспользоваться онлайн-сервисом здесь
Например, я попробовал это
std::vector<int> arrayOfProducts(const std::vector<int>amp; array)
{
std::vector<int> vec;
for (int i = 0; i < array.size(); i )
{
int leftidx = i - 1, rightidx = i 1;
int leftSum = 1, rightSum = 1, totalSum = 1;
if (leftidx >= 0){
while (leftidx >= 0){
leftSum *= array[leftidx];
leftidx--;
}
}
if (rightidx < array.size()) {
while (rightidx < array.size()) {
rightSum *= array[rightidx];
rightidx ;
}
}
totalSum = leftSum * rightSum;
vec.push_back(totalSum);
}
return vec;
}
static void TimeArrayOfProducts(benchmark::Stateamp; state)
{
for (auto _ : state) {
std::vector<int> temp;
temp.resize(state.range(0));
benchmark::DoNotOptimize(arrayOfProducts(temp));
}
}
BENCHMARK(TimeArrayOfProducts)
->RangeMultiplier(2)->Range(1<<8, 1<<12)->Complexity(benchmark::oN);
Кстати, то, что вы пытаетесь сделать, известно как частичная сумма, и вы можете переписать код как…
#include <numeric>
// requires C 20
std::vector<int> arrayOfProducts2(const std::vector<int>amp; in)
{
std::vector<int> frd_sum;
std::vector<int> bck_sum;
std::vector<int> resu<
frd_sum.resize(in.size());
bck_sum.resize(in.size());
result.resize(in.size());
std::partial_sum(in.begin(), in.end(), frd_sum.begin());
std::partial_sum(in.rbegin(), in.rend(), bck_sum.begin());
std::transform(frd_sum.begin(), frd_sum.end(), bck_sum.begin(), result.begin(), [](int a, int b){return a*b;});
return resu<
}
Что происходит быстрее, потому что…
- Он должен иметь O(n) сложность
- Многие чипы (Intel) имеют аппаратную оптимизацию для очень маленьких циклов.