[Powered by Google Translate] టామీ: ఎంపిక విధమైన పరిశీలించి, ఒక అల్గోరిథం తీసుకుందాం
సంఖ్యల జాబితా తీసుకుని వాటిని క్రమీకరించడానికి.
యాంత్రిక పద్ధతి గుర్తుంచుకోండి కేవలం ఒక దశల అడుగు
ఒక విధిని పూర్తి ప్రక్రియ.
ఎంపిక విధమైన వెనుక ప్రధాన ఆలోచన విభజించాలనే ఉంది
రెండు భాగాలు గా మా జాబితా -
ఒక క్రమబద్ధీకరించబడతాయి భాగం మరియు ఒక క్రమబద్ధీకరించనిది భాగం.
అల్గోరిథం యొక్క ప్రతి దశ, ఒక సంఖ్య నుండి తరలించిన
చివరికి వరకు క్రమబద్ధీకరించబడతాయి భాగానికి క్రమబద్ధీకరించనిది భాగం
మొత్తం జాబితా క్రమీకరించబడింది.
ఇక్కడ ఆరు సంఖ్యల జాబితా ఉంది -
23, 42, 4, 16, 8, మరియు 15.
ప్రస్తుతం మొత్తం జాబితా క్రమబద్ధీకరించనిది భావిస్తారు.
16 వంటి అనేక ఇప్పటికే దాని సరైన లో ఉన్నప్పటికీ
నగర, మా అల్గోరిథం వరకు తెలుసుకునేందుకు ఎటువంటి మార్గం ఉంది
మొత్తం జాబితా క్రమీకరించబడింది.
మేము క్రమం వరకు మేము క్రమబద్ధీకరించనిది చేయడానికి ప్రతి సంఖ్య పరిగణనలోకి చేస్తాము
అది మేమే.
మేము జాబితా క్రమంలో ఉండాలనుకుంటున్నాను తెలుసు.
కాబట్టి మేము మా జాబితాలో క్రమబద్ధీకరించబడతాయి భాగాన్ని నిర్మించేందుకు చెయ్యవచ్చును
ఎడమ నుండి కుడికి, అతిపెద్ద చిన్న.
ఆ చేయుటకు మేము కనీసం క్రమబద్ధీకరించనిది మూలకం కనుగొనేందుకు చేయాలి
మరియు క్రమబద్ధీకరించబడతాయి భాగం చివరిలో ఉంచారు.
ఈ జాబితా వర్గీకరించరు కాబట్టి, ఆ విధంగా చేయడానికి ఏకైక మార్గం
గుర్తు, క్రమబద్ధీకరించనిది భాగంలో ప్రతి మూలకం చూడండి
మూలకం అత్యల్ప మరియు పోల్చడం ఇది
ఆ ప్రతి మూలకం.
కాబట్టి మేము మొదటి 23 లో పరిశీలిస్తాము.
ఈ మేము చూసిన మొదటి మూలకం, కాబట్టి మేము గుర్తు చేస్తాము
కనీస గా.
తదుపరి మేము 42 వద్ద పరిశీలిస్తాము.
42 23 కంటే ఎక్కువగా ఉంది, కాబట్టి 23 ఇప్పటికీ కనీస ఉంది.
తదుపరి 23 కంటే తక్కువ 4, కాబట్టి మేము 4 గుర్తు చేస్తాము
కొత్త కనీస వంటి.
తదుపరి కాబట్టి 4, 4 కంటే ఎక్కువగా ఉంది, ఇది 16
ఇప్పటికీ కనీస ఉంది.
8 4 కంటే ఎక్కువగా ఉంది, మరియు 15 4 కంటే ఎక్కువగా ఉంది, 4 చేయాలి
చిన్న క్రమబద్ధీకరించనిది మూలకం.
కాబట్టి అయినప్పటికీ మనుషులుగా మనం వెంటనే 4 అని చూడగలరు
కనీస మూలకం, మా అల్గోరిథం కు అవసరం
మేము 4 దొరకలేదు తర్వాత కూడా ప్రతి క్రమబద్ధీకరించనిది మూలకం, -
కనీస మూలకం.
కాబట్టి ఇప్పుడు మేము కనీసం మూలకం, 4 దొరకలేదు చేసిన, మేము చెయ్యవచ్చును
జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం గా తరలించడానికి.
ఈ మొదటి మెట్టు కాబట్టి, ఈ మేము వద్ద 4 ఉంచాలి కావలసిన అర్థం
జాబితా ప్రారంభం.
ప్రస్తుతం 23 కాబట్టి, జాబితా ప్రారంభంలో ఉంది
యొక్క 4 మరియు 23 స్వాప్ తెలియజేయండి.
కాబట్టి ఇప్పుడు మా జాబితా ఈ కనిపిస్తోంది.
ఇది ఎందుకంటే మేము, 4 తుది నగర ఉండాలి తెలుసు
ప్రారంభంలో చిన్న మూలకం మరియు మూలకం రెండు
జాబితా యొక్క.
మేము ఎప్పుడైనా మళ్ళీ తరలించే లేదు ఈ అని చెప్పుకుంటారు.
కాబట్టి యొక్క మరొక మూలకం జోడించడానికి ఈ విధానాన్ని పునరుక్తి తెలియజేయండి
జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం.
ఇది ఎందుకంటే మేము, మేము 4 కు లేదు తెలుసు
ఇప్పటికే క్రమబద్ధీకరించబడతాయి.
కనుక మేము గుర్తుంచుకోవాలి మేము, 42 వద్ద ప్రారంభించవచ్చు
కనీస మూలకం.
తరువాత మేము 42 కంటే తక్కువ 23 చూడండి, అలా చేస్తాము మేము
23 కొత్త కనీస ఉంది గుర్తుంచుకోవాలి.
తదుపరి మేము, కంటే తక్కువ 23 ఇది 16 చూడండి
16 కొత్త కనీస ఉంది.
ఇప్పుడు మేము, కంటే తక్కువ 16 ఇది 8 చూడండి
8 కొత్త కనీస ఉంది.
చివరకు 8 కంటే తక్కువ 15, కాబట్టి మేము 8 కనీసం అని తెలుసు
క్రమబద్ధీకరించనిది మూలకం.
కాబట్టి మేము క్రమబద్ధీకరించబడతాయి నుండి 8 జోడించు ఉండాలి అర్థం
జాబితా యొక్క భాగం.
ప్రస్తుతం 4 మాత్రమే క్రమబద్ధీకరించబడతాయి మూలకం, కాబట్టి మేము ఉంచాలనుకుంటే
4 నుండి 8 తర్వాత.
42 నుంచి క్రమబద్ధీకరించనిది భాగంలో మొదటి అంశం
జాబితా, మేము 42 మరియు 8 స్వాప్ చెయ్యవచ్చును.
కాబట్టి ఇప్పుడు మా జాబితా ఈ కనిపిస్తోంది.
4 మరియు 8 జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం సూచిస్తాయి, మరియు
మిగిలిన సంఖ్యలు క్రమబద్ధీకరించనిది ప్రాతినిధ్యం
జాబితా యొక్క భాగం.
కాబట్టి యొక్క మరొక మళ్ళా కలిసి చెయ్యనివ్వండి.
మేము చూడండి లేదు నుండి మేము, 23 ఈ ప్రారంభమవుతుంది
4 మరియు ఇకపై 8 వారు ఉంచిన ఎందుకంటే
ఇప్పటికే క్రమబద్ధీకరించబడతాయి చేయబడింది.
16 కంటే తక్కువ 23, కాబట్టి మేము గుర్తు చేస్తాము
కొత్త కనీస వంటి 16.
15 చేయాలి, 16 కంటే తక్కువ 42, కానీ 15 కంటే తక్కువ 16
కనీస క్రమబద్ధీకరించనిది మూలకం.
కాబట్టి ఇప్పుడు మేము 15 మరియు 23 మారడానికి కావలసిన
మాకు ఈ జాబితా ఇవ్వండి.
జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం 4, 8 మరియు 15 ఉన్నాయి, మరియు
ఈ అంశాలను ఇప్పటికీ క్రమబద్ధీకరించనిది ఉంటాయి.
కానీ ఇది కేవలం కాబట్టి జరుగుతుందని తదుపరి క్రమబద్ధీకరించనిది మూలకం, 16,
ఇప్పటికే క్రమబద్ధీకరించబడింది.
అయితే, తెలిసి మా అల్గోరిథం కోసం మార్గం లేదు అని 16
ఇప్పటికే దాని సరైన స్థానంలో, కాబట్టి మేము ఇంకా అవసరం
అదే విధానాన్ని పునరుక్తి.
కాబట్టి, మేము 16 కంటే తక్కువ 42 ఉందని, మరియు 16 కంటే తక్కువ 23 ఉంది
16 కనీస మూలకం ఉండాలి.
ఇది కూడా ఈ మూలకం మారడానికి అసాధ్యం, మేము చేయగలరా
కేవలం ఈ ప్రదేశంలో వదిలి.
కాబట్టి మేము మా అల్గోరిథం యొక్క మరొక పాస్ అవసరం.
42 23 కంటే ఎక్కువ, కాబట్టి 23 ఉండాలి
కనీస క్రమబద్ధీకరించనిది మూలకం.
ఒకసారి మేము మా చివరి ముగిసేవి, 23 మరియు 42 స్వాప్
పేర్చిన జాబితా -
4, 8, 15, 16, 23, 42.
మేము ఇది నుంచి 42 సరైన స్థానంలో ఉండాలి తెలుసు
మాత్రమే మూలకం వదిలి, మరియు ఎంపిక విధమైన ఉంది.
లెట్ యొక్క కొన్ని ఇప్పుడు మన అల్గోరిథం ప్రమాణీకరించవల్సిన
pseudocode.
రేఖ ఒక న, మేము పైగా ఇంటిగ్రేట్ అవసరమైన చూడగలరు
జాబితా యొక్క ప్రతీ మూలకం.
గత మూలకం తప్ప, ఎందుకంటే 1 మూలకం
జాబితా ఇప్పటికే క్రమబద్ధీకరించబడింది.
లైన్ రెండు న, క్రమబద్ధీకరించనిది మొదటి మూలకం పరిగణలోకి
మేము మా వలె జాబితా యొక్క భాగం, కనీస అని
ఉదాహరణకు, కాబట్టి మేము పోల్చడానికి ఏదైనా కలిగి.
లైన్ మూడు మేము పైగా iterate రెండవ లూప్ ప్రారంభమవుతుంది
ప్రతి క్రమబద్ధీకరించనిది మూలకం.
మేము తెలిసిన నేను నిద్రావస్థ తర్వాత, క్రమబద్ధీకరించబడింది భాగం
మా జాబితా ప్రతి అడుగు నుండి అది నేను అంశాలను కలిగి ఉండాలి
రకాల ఒక మూలకం.
కాబట్టి మొదటి క్రమబద్ధీకరించనిది మూలకం స్థానం i ప్లస్ 1 ఉండాలి.
లైన్ నాలుగు న, కనీస ప్రస్తుత మూలకం పోల్చి
మేము ఇప్పటివరకు చూసిన ఆ మూలకం.
ప్రస్తుత మూలకం కనీస తక్కువైతే
మూలకం, అప్పుడు మేము కొత్త గా ప్రస్తుత మూలకం గుర్తు
లైన్ ఐదు న కనిష్ట.
చివరగా, పంక్తులు ఆరు మరియు ఏడు న, కనీస మార్పిడి
తద్వారా మొదటి క్రమబద్ధీకరించనిది మూలకం తో మూలకం,
జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం జోడించడం.
మేము ఒక అల్గోరిథం తర్వాత, ఒక ముఖ్యమైన ప్రశ్న అడగడానికి
మేమే ప్రోగ్రామర్లు ఆ ఎంత సమయం పడుతుంది లేదు ఉంది?
మేము మొదటి ప్రశ్న అడుగుతాము ఎంత ఈ కోసం పడుతుంది
అల్గోరిథం విషయంలో అమలు చెయ్యడానికి?
మేము ఈ పరుగు ప్రాతినిధ్యం రీకాల్
పెద్ద O సంజ్ఞామానం సమయం.
కనీస క్రమబద్ధీకరించనిది మూలకం నిర్ధారించేందుకు, మేము
ముఖ్యంగా జాబితా ప్రతి మూలకం పోల్చి వచ్చింది
జాబితాలో ప్రతి ఇతర మూలకం.
Intuitively, n స్క్వేర్డ్ ఆపరేషన్ యొక్క O వంటి ఈ శబ్దాలు.
మా pseudocode వద్ద గురించి, మేము కూడా లోపల యున్న ఒక లూప్ కలిగి
ఒక O వంటి నిజానికి వినిపిస్తుంది మరొక లూప్,
n స్క్వేర్డ్ ఆపరేషన్.
అయితే, మేము చూసి అవసరం లేదు గుర్తుంచుకోవాలి
కనీస క్రమబద్ధీకరించనిది మూలకం నిర్ణయించేటప్పుడు మొత్తం జాబితా?
మేము 4 క్రమబద్ధీకరించబడతాయి అని తెలుసు ఒకసారి, ఉదాహరణకు, కాదు
దాన్ని మళ్ళీ వద్ద చూడవలసిన అవసరం.
ఈ నడుస్తున్న సమయంలో తక్కువ చేస్తుంది?
పొడవు 6 మా జాబితా కోసం, మేము ఐదు అవసరమైన
మొదటి మూలకం కోసం పోలికలు, నాలుగు పోలికలు
రెండవ మూలకం, అందువలన న.
ఆ దశలను మొత్తం మొత్తానికి అర్థం
1 నుండి జాబితా మైనస్ 1 యొక్క పొడవు వరకు పూర్ణాంకాల.
మేము ఒక సమ్మషన్ ఈ సూచిస్తుంది.
మేము ఇక్కడ summations లోకి కాదు.
కానీ ఈ సమ్మషన్ n సార్లు సమానంగా ఉంటుంది అవుతుంది
n మైనస్ 2 పైగా 1.
లేదా సమానమైన, n 2 పై మైనస్ n 2 పై Squared.
Asymptotic runtime గురించి మాట్లాడుతూ, ఈ n స్క్వేర్డ్ పదం
ఈ n పదం ఆధిపత్యం అన్నారు.
కాబట్టి ఎంపిక విధమైన n స్క్వేర్డ్ ఓ ఉంటుంది.
మా ఉదాహరణ లో, ఎంపిక విధమైన ఇప్పటికీ అవసరమైన గుర్తుచేసుకున్నారు
తనిఖీ ఉంటే ఇప్పటికే క్రమబద్ధీకరించబడతాయి ఒక సంఖ్య
తరలించేందుకు అవసరమైన.
కాబట్టి అని మేము ఇప్పటికే పైగా ఎంపిక విధమైన నడిచింది ఉంటే
జాబితా క్రమబద్ధీకరించిన అది వంటి దశలను అదే నెంబర్ కావాలి
పూర్తిగా క్రమబద్ధీకరించనిది జాబితా పైగా పరిగెడుతున్నప్పుడు చేస్తాను.
కాబట్టి ఎంపిక విధమైన, స్క్వేర్డ్ n యొక్క ఒక ఉత్తమ కేసు ప్రదర్శన ఉంది
ఇది మేము ఒమేగా n స్క్వేర్డ్ తో సూచిస్తాయి.
మరియు ఎంపిక విధమైన కోసం ఇది.
మేము అనేక అల్గోరిథంలు ఒకటి
ఒక జాబితాను క్రమబద్దీకరించేందుకు ఉపయోగించండి.
నా పేరు టామీ, మరియు ఈ cs50 ఉంది.