בתשובה לירדן ניר-בוכבינדר, 30/05/04 0:14
 |
|
 |
||
|
||||
 |
שיקול מעניין. ומה הסיבוכיות של *סכום* כל המספרים עד N? |  |
 |
 |
|
|
|
||
|
||||
|
כמו הסיבוכיות של חיבור 1, כפל שני מספרים, וחילוק ב-2. בקיצור, כמו כפל. | |
|
|
|
|
|
||
|
||||
|
ידעתי שמישהו יתחכם. תחליף ''חיבור'' ב''פעולה שאין נוסחה סגורה לחישוב'' למשל חיבור ההופכיים ( מחושבים לדיוק יחסי מסויים). | |
|
|
|
|
|
||
|
||||
|
אז לא הבנתי. תלוי בסיבוכיות של ה"חיבור". אם אין איזה טריק מיוחד, אתה עושה N פעמים את הפעולה, לא? | |
|
|
|
|
|
||
|
||||
|
לעשות פעולה N פעמים זה סיבוכיות אקספוננציאלית בN. אני רק רציתי להאיר את העניין בלי להשתמש בעצרת, שיש לזה קוננוטציות של משהו (סופר) אקסספוננציאלי בלאו הכי. מה שמחזיר אותי למחשב הקוונטי- האם ניתן להגיד שמחשב קוונטי מחליף את הסיבוכיות של החישוב בסיבוכיות של הכנת הקלט? הרי צריך לאתחל שתיים בחזקת N קטים כדי לבצע חישוב. |
|
|
|
|
|
|
||
|
||||
|
לעשות פעולה N פעמים זה סיבוכיות אקספוננציאלית ב*אורך של N*, כלומר אקספוננציאלית ב*לוג N*, כלומר *לינארית ב-N*. לא ללכת לאיבוד, ולא להתבלבל בסימנים! |
|
|
|
|
|
|
||
|
||||
|
גם אתה נודניק? שיהיה ב*אורך* של N אם זה מרגיע אותך. הכוונה הייתה שאורך הקלט הוא לוג N ומספר הפעולות הוא N, בדיוק כמו שירדן כתב. לא ללכת לאיבוד, ולא להוציא דברים מהקשרם. |
|
|
|
|
|
|
||
|
||||
|
אני חייב להיות נודניק. זה כתוב בכתובת המייל שלי :-) ------ אביב, שכתב כבר הרבה יותר מידי בשביל סו"ש אחד, והצליך לעבוד על עצמו עם מלכודת האיילים, למרות שהוא כותב רק ממחשב אחד. הוא מפסיק עכשיו. |
|
|
|
|
|
|
||
|
||||
|
אני חושב שיש כאן בלבול קטן: הקונטציה ה(סופר)-אקספוננציאלית של עצרת היא בגלל אלגוריתמים שהם ב"סיבוכיות עצרת", לא בגלל חישוב עצרת כשלעצמה. אבל אתה צודק שיש נטיה לבלבל בשנייה הראשונה (גם אצלי), ולכן, מבחינה דרמטורגית, עדיף לשאול את השאלה על אלגוריתם יותר טריוויאלי. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |