сумма всех arr [j], где i делит j

Question

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

Я написал ниже код. Но это грубая сила. Могу ли я стать лучше, чем это

#include<stdio.h> 

int main() { 
    int n, q; 
    int mod = 1000000000 + 7; 
    scanf("%d", &n); 

    int arr[n+1]; 
    int i; 
    for (i = 1; i <= n ; ++i) { 
     scanf("%d", &arr[i]); 
    } 

    int p; 
    scanf("%d", &p); 
    int sum = 0; 
    int j; 
    for(j = p; j <= n; j = j+p) { 
     sum = (sum + arr[j]) % mod; 
    } 
    printf("%d\n",sum); 
    return 0; 
} 

Answer 1

Вы замечаете, что ваш пример реализации является «грубой силой» и спрашивает, можете ли вы «сделать лучше». Грубая сила обычно подразумевает подход, который просто реализовать, но выполняет значительно большую работу или использует значительно большую память, чем это теоретически необходимо. Это предполагает выделение огромных ресурсов вместо эффективной работы. Часто «существенно больше» сводится к таким подходам, имеющим более высокую асимптотическую сложность, чем наилучшие возможные подходы.

Ваш пример реализации не такой. Для добавления n/p для произвольных чисел требуется n/p операций, поэтому O(n) - наименьшая асимптотическая сложность, которую может иметь алгоритм задачи. Это асимптотическая сложность вашей реализации, поэтому она не может быть улучшена в этом смысле.

Кроме того, ваша реализация, похоже, выполняет примерно столько же операций, сколько вы могли бы надеяться. Рассмотрим эту наивную альтернативу, хуже реализация цикла суммирования:

for(j = 1; j <= n; j++) { 
     if (j % p == 0) { 
      sum = (sum + arr[j]) % mod; 
     } 
    } 

Это можно рассматривать как несколько более прямой перевод требований в код C. Хотя это все еще только O (n), его можно было бы охарактеризовать как реализацию грубой силы из-за (p-1) -кратного превышения приращений до j и вычислений n от j % p, оба из которых исключают вашу реализацию.

Итог: нет, нет более эффективной реализации, чем тот, который вы представляете.