system.out.println

Question

की समय जटिलता मुझे एल्गोरिदम पर मेरे पाठ्यक्रम पर अलग-अलग चीजें बताई गई हैं, और यह सोच रहा था कि क्या मुझे जावा के System.out.println() कमांड की जटिलता के बारे में एक निश्चित उत्तर मिल सकता है।

उदाहरण के लिए, एन के संबंध में निम्नलिखित की जटिलता क्या होगी?

String stringy = ""; 
while(stringy.length() < N) { 
    System.out.println(stringy); 
    stringy += "X"; 
} 

नए लड़के की मदद करने के लिए धन्यवाद!

Answer 1

इस कोड की समय जटिलता ओ (एन * एन) है क्योंकि यह प्रिंट के एन गुना का एक लूप है। मुझे नहीं पता कि आपको क्या बताया गया है लेकिन प्रिंटिंग की समय जटिलता जावा में ओ (एन) से भी बदतर नहीं है।

अपने कोड में

आप प्रत्येक पंक्ति को "एक्स" जोड़ने के लिए, और की वजह से आपका प्रिंटिंग होगा:

X 
XX 
XXX 
XXXX 
XXXXX 
XXXXXX 
. 
. 
. 

तो यह जटिलता एक Arithmetic progression के रूप में गणना की जाती है और हम पाते हैं:

(1+N)*N/2=O(N^2) 

को इस आदेश को पढ़ें कि आप कैसे काम कर सकते हैं here या here:

एक सामान्य धारणा है कि प्रदर्शन में एसओपी खराब हैं। जब हम गहराई से विश्लेषण करते हैं, तो कॉल का अनुक्रम println -> प्रिंट -> लिखना() + newLine() जैसा है। यह अनुक्रम प्रवाह सूर्य/ओरेकल जेडीके का कार्यान्वयन है। दोनों लिखने() और newLine() में सिंक्रनाइज़ ब्लॉक शामिल है। सिंक्रनाइज़ेशन में थोड़ा ओवरहेड होता है, लेकिन से अधिक बफर और प्रिंटिंग में वर्ण जोड़ने की लागत अधिक है।

जब हम प्रदर्शन विश्लेषण चलाते हैं, तो एसओपी और की कई संख्याएं रिकॉर्ड करें, निष्पादन अवधि आनुपातिक रूप से बढ़ जाती है। प्रदर्शन घटता है जब हम 50 वर्णों को प्रिंट करते हैं और 50,000 से अधिक पंक्तियों को प्रिंट करते हैं।

यह सब उस परिदृश्य पर निर्भर करता है जिसका हम उपयोग करते हैं। जो कुछ भी हो सकता है, stdout पर लॉगिंग के लिए System.out.println का उपयोग न करें।

Answer 2

System.out.println(stringy); कमांड की समय जटिलता ???

आप मूल रूप से मतलब कोड के समय जटिलता झलकी above.Look, समय जटिलता विशेष रूप से एक विशिष्ट कोड या भाषा से संबंधित नहीं है यह मूल रूप से इसका मतलब है समय कितना सैद्धांतिक रूप से कोड की लाइन द्वारा ले जाया जाएगा।

: अपने कोड के इस हिस्से में अब (बहुपद समीकरणों को हल करने के मामले में)

• इनपुट बहुपद का
• डिग्री के आकार: यह आमतौर पर दो या तीन बातों पर निर्भर करता

  String stringy = ""; 
  while(stringy.length() < N) {// the loop will execute in order of N times 
      System.out.println(stringy);//println will execute in order of N times too as in printing each character 
      stringy += "X"; 
  } 
  

  यह स्पष्ट रूप से इनपुट के आकार पर निर्भर करेगा जो निश्चित रूप से स्ट्रिंग की लंबाई है। सबसे पहले जबकि लूप एन से थोड़ा कम निष्पादित करता है (stringy.length() < N की स्थिति के कारण यह <= इसे स्ट्रिंग की पूरी लंबाई के माध्यम से चलाएगा) जिसे हम एन के क्रम में कह सकते हैं और स्ट्रिंग को प्रिंट करने के क्रम में किया जाएगा एन के कुल कोड में O(N^2)

Answer 3

इस कोड की जटिलता O(n^2) है। यह लूप एन बार को पुन: सक्रिय करता है, और क्योंकि System.out.println प्रत्येक वर्ण को मुद्रित करना चाहिए, जो 0 से एन वर्णों से प्रत्येक पुनरावृत्ति को मुद्रित करता है, औसत एन/2 औसत, आप स्थिर, एन * एन = एन^2 ड्रॉप करते हैं। इसी तरह, स्ट्रिंग में जोड़ने से पूरी स्ट्रिंग को कॉपी किया जा रहा है (स्ट्रिंग जावा में अपरिवर्तनीय हैं, इसलिए किसी भी बदलाव का मतलब है कि आपको पूरी स्ट्रिंग को एक नई स्ट्रिंग में कॉपी करना होगा)। यह एक और रैखिक ऑपरेशन है। तो आपके पास n * (n/2 + n/2) अभी भी एक वर्गबद्ध क्रम पर है - O(n^2)।

String stringy = ""; 
while(stringy.length() < N) { // will iterate N times 
    System.out.println(stringy); // has to print N letters 
    stringy += "X"; // has to copy N letters into a new string 
} 

Answer 4

समय जटिलता आपको बताता है कि और अधिक काम अपने एल्गोरिथ्म इनपुट आकार की वेतन वृद्धि प्रति करते हैं, दे या कुछ निरंतर गुणांक लेने के लिए है कि कैसे।

तो हे (2 एन) के एक ऊपरी बाध्य जटिलता है कि गुणांक चाहे कितना किसी भी संख्या हो सकती है क्योंकि वास्तविक परिभाषा यहां पाया

http://en.wikipedia.org/wiki/Big_O_notation

राज्यों जटिलता ओ (23,587 एन) के बराबर है बड़ा, जब तक यह इनपुट के आकार के संबंध में तय किया जाता है।

क्योंकि आप 'एन' पाश के भीतर उपयोग नहीं कर रहे हैं, तो आप सिर्फ एक स्ट्रिंग के लिए पर एक चार जोड़ रहे हैं, यात्रा प्रति काम की राशि है जो आप कितने पुनरावृत्तियों है के बराबर है -> हे (एन)

यदि आपके पास "स्ट्रिंग + = स्ट्रिंग" था; बजाय यह हे (एन^2) प्रत्येक यात्रा आप काम की राशि को दोगुना कर रहे हैं करने के लिए आपके पास हो सकता है क्योंकि

* * नोट

मैं यह सोचते हैं हूँ system.out.print एक परमाणु बयान है, यानी यह .. एक भी कार्रवाई के रूप में सभी पात्रों प्रिंट अगर यह व्यक्तिगत रूप से तो इसकी हे (एन^2) ....

Answer 5

एक महान जवाब यहां पाया जा सकता हर किरदार मुद्रित: http://www.quora.com/What-exactly-is-the-time-complexity-for-System-out-println-in-Java-O-1-or-O-N

मुख्य विचार यह है कि एक स्ट्रिंग को प्रिंट करना वास्तव में इसे stdout पर कॉपी कर रहा है - और हम जानते हैं कि एक स्ट्रिंग की प्रति ओ (एन) है।

दूसरे भाग का कहना है कि आप समय की एक बड़ी संख्या में प्रिंट करके कर सकते हैं: - एक चरित्र - एक बहुत बड़ी स्ट्रिंग और तुम समय अंतर देखेंगे !! (यदि मुद्रण ओ (1) होगा तो आप नहीं करेंगे)