בתשובה לראובן, 30/05/04 13:11
מאחורי כל זה מסתתר O של גדול 222169
כמו הסיבוכיות של חיבור 1, כפל שני מספרים, וחילוק ב-‏2. בקיצור, כמו כפל.
222182
ידעתי שמישהו יתחכם. תחליף ''חיבור'' ב''פעולה שאין נוסחה סגורה לחישוב'' למשל חיבור ההופכיים ( מחושבים לדיוק יחסי מסויים).
222184
אז לא הבנתי. תלוי בסיבוכיות של ה"חיבור". אם אין איזה טריק מיוחד, אתה עושה N פעמים את הפעולה, לא?
אבל כמו שירדן הראה- 222186
לעשות פעולה N פעמים זה סיבוכיות אקספוננציאלית בN. אני רק רציתי להאיר את העניין בלי להשתמש בעצרת, שיש לזה קוננוטציות של משהו (סופר) אקסספוננציאלי בלאו הכי.
מה שמחזיר אותי למחשב הקוונטי- האם ניתן להגיד שמחשב קוונטי מחליף את הסיבוכיות של החישוב בסיבוכיות של הכנת הקלט? הרי צריך לאתחל שתיים בחזקת N קטים כדי לבצע חישוב.
לא לא לא לא לא 222198
לעשות פעולה N פעמים זה סיבוכיות אקספוננציאלית ב*אורך של N*, כלומר אקספוננציאלית ב*לוג N*, כלומר *לינארית ב-N*.

לא ללכת לאיבוד, ולא להתבלבל בסימנים!
שופכים את דמי! 222200
גם אתה נודניק? שיהיה ב*אורך* של N אם זה מרגיע אותך. הכוונה הייתה שאורך הקלט הוא לוג N ומספר הפעולות הוא N, בדיוק כמו שירדן כתב.

לא ללכת לאיבוד, ולא להוציא דברים מהקשרם.
שופכים את דמי! 222202
אני חייב להיות נודניק. זה כתוב בכתובת המייל שלי :-)

------
אביב, שכתב כבר הרבה יותר מידי בשביל סו"ש אחד, והצליך לעבוד על עצמו עם מלכודת האיילים, למרות שהוא כותב רק ממחשב אחד. הוא מפסיק עכשיו.
עצרת המונים 222292
אני חושב שיש כאן בלבול קטן: הקונטציה ה(סופר)-אקספוננציאלית של עצרת היא בגלל אלגוריתמים שהם ב"סיבוכיות עצרת", לא בגלל חישוב עצרת כשלעצמה. אבל אתה צודק שיש נטיה לבלבל בשנייה הראשונה (גם אצלי), ולכן, מבחינה דרמטורגית, עדיף לשאול את השאלה על אלגוריתם יותר טריוויאלי.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים