algorithm - असिमप्टोोटिक विश्लेषण




math asymptotic-complexity (2)

मुझे यह समझने में परेशानी हो रही है कि यह कैसे एक सूत्र में बना सकता है।

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j += i) {

मुझे पता है कि क्या होता है, हर आई ++ के लिए आपके पास 1 स्तर का गुणन कम है।

मैं = 1, आपको जम्मू = 1, 2, 3, ..., 100 मिलता है

मैं = 2, आपको जे = 1, 3, 5, ..., 100 मिलता है

मुझे यकीन नहीं है कि बिग-थेटा के मामले में यह कैसे सोचें।

जम्मू की कुल संख्या N, N / 2, N / 3, N / 4 ..., N / N (मेरा निष्कर्ष)

एन के एक समारोह के रूप में यह कोशिश करने और सोचने के लिए सबसे अच्छा कैसे होगा?


तो आपका सवाल वास्तव में कम हो सकता है "हार्मोनिक श्रृंखला 1/1 + 1/2 + 1/3 + ... + 1 / एन के लिए कसौटी क्या है?" जिसके लिए उत्तर log N (आप इसे असतत के बजाय निरंतर योग के रूप में देख सकते हैं, और ध्यान दें कि 1/N का अभिन्न log N )

आपकी हार्मोनिक श्रृंखला पूरे एल्गोरिदम का सूत्र है (जैसा आपने सही तरीके से निष्कर्ष निकाला है)

तो, आपकी राशि:

N + N/2 + N/3 + ... + N/N = N * (1 + 1/2 + 1/3 + ... + 1/N) = Theta(N * log N)

इसलिए एल्गोरिथ्म के लिए तंग बाध्य है N*log N

यहां [कठोर] गणितीय सबूत देखें ("इंटीग्रल टेस्ट" और "विचलन दर" हिस्सा देखें)


ठीक है, आप सिग्मा नोटेशन की पद्धति से उपयोग कर सकते हैं:





big-theta