Дұрыс әрі жеткілікті жылдам алгоритм

Картадағы орнымыз

Бұл бір жобаның үшінші бөлімі. 0.2 нұсқасының деректерін қолданамыз, бірақ әрекеттерді әзірге қағазда сипаттаймыз: Python жазбай тұрып қатені табуға болады.

Жағдай және сұрақ

Үш тапсырмадағы бірдей id көзге бірден түседі. Ал жазба мың болса, қайталауды қалай тез әрі сенімді табамыз? Жылдамдықты талқыламас бұрын, нені қайталау деп санайтынымызды және қандай жауап күтетімізді анықтаймыз.

Жаңа сөздерді анық түсінейік

Дұрыстық — алгоритмнің бір мысалда емес, барлық жарамды кірісте жазылған келісімді орындауы. Қарсы мысал — уәде бұзылатын кіріс. Тиімділік — кіріс өскендегі әрекет пен жад шығынын салыстыру. Кіріс өлшемі n — мұнда тапсырма саны. Сызықтық өту әр жазбаны шамамен бір рет қарайды. Квадраттық өсу әр жазбаны басқаларымен салыстырғанда пайда болады: жұп саны n(n−1)/2. Жиын — қайталанбайтын мәндер коллекциясы, онда id бұрын кездескенін әдетте тез тексеруге болады; бірақ қосымша жад қажет. Күрделілік өсу сипатын көрсетеді, нақты ноутбуктағы секундқа кепіл емес.

Сабақтың тірек сигналы

әуелі келісім мен қарсы мысал → кейін әрекет саны мен жад

Қадамдап талдаймыз

A тәсілі: әр тапсырманың id мәнін кейінгілермен салыстыру. 4 тапсырмада 6 жұп, 10 тапсырмада 45 жұп. B тәсілі: бос seen жиынымен солдан оңға өту; id ішінде болса, қайталау табылды, болмаса қосу. t-01,t-02,t-03,t-02 үшін B: алғашқы үшеуін қосып, төртіншісінде қайталауды табамыз. 4 жазбада ең көбі 4 кіріс мәні тексеріледі, бірақ бұрынғыларды сақтау керек. Атауды емес, id салыстырыңыз: екі бөлек тапсырманың атауы бірдей болуы мүмкін.

Қолмен тексеру

Төрт id жазыңыз: t-01, t-02, t-03, t-02. Жұппен тексеруде 1–2, 1–3, 1–4, 2–3, 2–4, 3–4 орын жұптарын сызыңыз; қайталау бесінші жұпта табылады. Енді seen жиынын жүргізіңіз: алғашқы үш қадамнан кейін үш мән бар, төртіншісінде t-02 бұрыннан кездеседі. Жұмысты санағанда нені санайтыныңызды атаңыз: жұп салыстыру ма, жиында барын тексеру ме. 5 пен 4 әртүрлі әрекет саны; нақты жылдамдық кейін өлшенеді.

Болжаңыз және тексеріңіз

Бос тізімде және бір id үшін не шығады? Екеуінде де қайталау жоқ. t-01,t-01 үшін? Екіншісінде табылады. t-01 мен T-01 болса, жауап алдын ала жазылған регистр ережесіне тәуелді; регистрді үнсіз ауыстырмаңыз.

Қатені табыңыз

«B кез келген құрылғыда, кез келген кірісте жылдам». Үлкен тізімде әдетте салыстыру аз, бірақ жиынға жад кетеді және іске асыру маңызды. Таңдауды талапқа сүйеніп жасаңыз, код дайын болғанда нақты өлшеңіз; қағаз үлгіні бенчмарк деп атамаңыз.

Жаңа жағдайға көшіру

Мерзімдері сұрыпталған тізімнен ең жақынын іздеңіз. Рет кепілденсе, түгел қарау керек пе? Әуелі сұрыптау кепілдігін дәлелдеңіз, әйтпесе ерте тоқтау қате жауап беруі мүмкін.

Жобаға енгізілетін өзгеріс

ALGORITHM-kz.md ішіне қайталанатын id табудың екі тәсілін, n=1,4,10 жұп санын және t-01,t-02,t-01, бос тізім, атауы бірдей бірақ id бөлек жағдайларын енгізіңіз. Мәмілені жазыңыз: азырақ тексеру үшін қосымша жад.

Тапсырма және дәлел

Сыныптасыңыз атауды салыстыратын қате алгоритмге қарсы мысал тапсын. Кейін B тәсілін негіздесін: әр қадамнан соң seen дәл қаралған идентификаторларды сақтайды. Дәлел — трасса мен инвариант.

1, 7 және 30 күннен кейін қайталау

Ертең төрт жазбаға алты жұпты қалпына келтіріңіз. Жеті күннен соң бес жазбаның салыстыруын есептеңіз. Бір айдан кейін қағаз болжамды бағдарлама өлшемімен салыстырыңыз.

Келесі сабақ: Бақылау нүктесі: көмекші алгоритмдері қағазда