所有arr [j]的總和在哪裏我除以j

-1

什麼是最好的方式來找到所有元素的所有元素的索引可以被我整除的最小複雜性。所有arr [j]的總和在哪裏我除以j

我寫下面的代碼。但那是蠻力。我能比這更好嗎

#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; 
}

來源

2016-09-15 Mukesh Gupta

你必須檢查數組的所有元素，所以你不能比O（n）好。 –

好吧，你已經發布了C代碼......但是如果你認爲它不適用於特定語言，你可以將其標記爲「語言不可知」。 –

使用plain int時除法1億？這段代碼很腥，你確定你沒有得到整數溢出嗎？ – Lundin

你說你的示例實現是「蠻力」，並詢問你是否可以「做得更好」。蠻力通常意味着一種易於實現的方法，但執行更多的工作或使用比理論上必需的更多的內存。它建議投入大量資源取代高效運作。通常，「實質上更多」歸結爲具有比最佳可能方法更高的漸近複雜性的方法。

您的示例實現不是這樣的。添加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和的計算，您的實現都會避免這兩個增量。

底線：沒有，沒有比您提供的實施更高效的實施。

來源

2016-09-15 14:51:35

所有arr [j]的總和在哪裏我除以j

回答

相關問題