यूक्लिड के एल्गोरिदम समय जटिलता

Question

मेरे पास सबसे बड़ा आम divisors खोजने के लिए यूक्लिड के एल्गोरिदम के बारे में एक सवाल है।

जीसीडी (पी, क्यू) जहां पी> क्यू और क्यू एक एन-बिट पूर्णांक है।

मैं एल्गोरिथ्म पर एक समय जटिलता विश्लेषण का पालन करने के

gcd(p,q) 
    if (p == q) 
     return q 
    if (p < q) 
     gcd(q,p) 
    while (q != 0) 
     temp = p % q 
     p = q 
     q = temp 
    return p 

मैं पहले से ही समझ में (इनपुट एन-बिट के रूप में ऊपर है) कोशिश कर रहा हूँ कि दो संख्याओं का योग, u + v जहां u और v स्टैंड p और q के शुरुआती मूल्यों के लिए, कम से कम 1/2 के कारक से कम हो जाता है।

अब m इस एल्गोरिदम के लिए पुनरावृत्तियों की संख्या होने दें। हम सबसे छोटे पूर्णांक m जैसे (1/2)^m(u + v) <= 1

यहां मेरा प्रश्न है। मुझे लगता है कि प्रत्येक पुनरावृत्ति पर दो संख्याओं का योग (1/2)^m(p + q) द्वारा ऊपरी-बाध्य है। लेकिन मैं वास्तव में नहीं देखता कि अधिकतम मात्रा m तब तक पहुंच गई है जब यह मात्रा <= 1 है।

उत्तर ओ (एन) एन-बिट्स q के लिए है, लेकिन यह वह जगह है जहां मैं अटक गया हूं।

कृपया मदद !!

Answer 1

कल्पना कीजिए कि हमारे पास पी और क्यू है जहां पी> क्यू है। अब, दो मामले हैं:

1) पी> = 2 * क्यू: इस मामले में, पी को मॉड के बाद क्यू से कम कुछ कम कर दिया जाएगा, इसलिए राशि का अधिकतम 2/3 होगा पहले।

2) क्यू < पी < 2 * क्यू: इस मामले में, एक मॉड ऑपरेशन पी से क्यू घटाने जैसा होगा, इसलिए फिर से कुल योग पहले 2/3 के पहले होगा।

इसलिए, प्रत्येक चरण में यह योग अंतिम योग का 2/3 होगा। चूंकि आपकी संख्या एन बिट्स हैं, योग की परिमाण 2^{n + 1} है; इसलिए, लॉग 2^{एन + 1} (बेस 3/2) चरणों के साथ जो वास्तव में ओ (एन) है, योग 0.