[Powered by Google Translate] బహుశా మీరు ప్రజలు వేగంగా లేదా సమర్థవంతమైన అల్గోరిథం గురించి మాట్లాడేందుకు విన్న చేసిన
మీ పని అమలు,
కానీ ఫాస్ట్ లేదా సమర్ధంగా ఒక అల్గోరిథం కోసం ఖచ్చితంగా అర్థం ఏమిటి?
సరే,, నిజ సమయంలో ఒక కొలత గురించి మాట్లాడటం లేదు
సెకన్లు లేదా నిమిషాలు ఇష్టపడుతున్నారు.
ఇది కంప్యూటర్ హార్డ్వేర్
మరియు సాఫ్ట్వేర్ పూర్తిగా మారుతుంది.
నా కార్యక్రమం, మీదే కంటే నెమ్మదిగా అమలు కావచ్చు
నేను, ఒక పాత కంప్యూటర్ మీద నడుస్తున్న నేను ఎందుకంటే
లేదా నేను ఒక ఆన్లైన్ వీడియో గేమ్ ప్లే కావడం ఎందుకంటే
అదే సమయంలో, ఇది నా మెమరీ hogging ఉంది
లేదా నేను వివిధ సాఫ్ట్వేర్ ద్వారా నా ప్రోగ్రామ్ అమలు చేస్తూ ఉండవచ్చు
ఇది తక్కువ స్థాయిలో భిన్నంగా యంత్రం కమ్యూనికేట్.
ఇది యాపిల్స్ అండ్ ఆరెంజ్స్ పోల్చడం వంటిది.
నా నెమ్మదిగా కంప్యూటర్ సమయం పడుతుంది కనుక
మీది ఒక సమాధానం తిరిగి ఇవ్వాలని కంటే
మీరు మరింత సమర్థవంతంగా అల్గోరిథం కలిగి కాదు.
>> కాబట్టి, మేము నేరుగా కార్యక్రమాలను runtimes పోల్చి కాదు నుండి
సెకన్లు లేదా నిమిషాలు లో,
ఎలా మేము 2 వివిధ అల్గోరిథంలు పోల్చి లేదు
సంబంధం లేకుండా వారి హార్డ్వేర్ లేదా సాఫ్ట్వేర్ పర్యావరణం యొక్క?
క్రమసూత్ర సామర్థ్యం కొలిచే ఒక ఏకరీతిగా మార్గం సృష్టించడానికి,
కంప్యూటర్ శాస్త్రవేత్తలు మరియు గణిత రూపొందించారు
ఒక ప్రోగ్రామ్ యొక్క asymptotic సంక్లిష్టత కొలిచే భావనలు
మరియు టిప్పణి 'బిగ్ Ohnotation' అని
ఈ వివరించేందుకు.
లాంఛనప్రాయమైన నిర్వచనం అని ఒక ఫంక్షన్ f (x)
g క్రమాన్ని (x) అమలు
కొన్ని (x) విలువ ఉంది ఉంటే, x ₀ మరియు
కొన్ని స్థిరమైన, C, ఇది కోసం
f (x) కంటే తక్కువ లేదా సమానం
స్థిరమైన సార్లు g (x)
x ₀ కంటే ఎక్కువ అన్ని x కోసం.
>> కానీ అధికారిక నిర్వచనం ద్వారా దూరంగా భయపడ్డాను డోంట్.
ఈ నిజానికి సైద్ధాంతిక నిబంధనలు తక్కువ శతకము
Well, ఇది ప్రాథమికంగా విశ్లేషించడం ఒక మార్గం
ఒక ప్రోగ్రామ్ యొక్క రన్టైమ్ asymptotically పెరుగుతుంది ఎంత వేగంగా.
మీ ఇన్పుట్లను పరిమాణం అనంతం వైపు వల్ల ఆ, ఉంది
సే, మీరు పరిమాణం 10 యొక్క వ్యూహం పోలిస్తే పరిమాణం 1000 యొక్క వ్యూహం క్రమబద్ధీకరించేందుకు చేస్తున్నారు.
మీ ప్రోగ్రామ్ యొక్క రన్టైమ్ ఎలా పెరుగుతాయి లేదు?
ఉదాహరణకు, అక్షరాలు సంఖ్యపై ఊహించుకోండి
ఒక స్ట్రింగ్ లో సరళమైన మార్గం
మొత్తం స్ట్రింగ్ ద్వారా వాకింగ్ ద్వారా
లెటర్ ద్వారా లేఖ మరియు ప్రతి పాత్ర కోసం ఒక కౌంటర్ 1 జోడించడం.
ఈ అల్గోరిథం సరళ సమయంలో అమలు చెబుతారు
అక్షరాల సంఖ్య సంబంధించి,
స్ట్రింగ్ లో 'n'.
చిన్న లో, O (n) లో నడుస్తుంది.
ఎందుకు ఉంది?
Well, ఈ విధానాన్ని ఉపయోగించి, సమయం అవసరం
మొత్తం స్ట్రింగ్ ప్రయాణించేందుకు
అక్షరాల సంఖ్య నిష్పత్తిలో ఉంటుంది.
20 పాత్ర స్ట్రింగ్ లో అక్షరాలు సంఖ్యపై
అది పడుతుంది రెండుసార్లు కాలం పడుతుంది అన్నారు
ఒక 10-పాత్ర స్ట్రింగ్ లో అక్షరాలు లెక్కించడానికి,
మీరు అన్ని అక్షరాలు కు ఎందుకంటే
మరియు ప్రతి పాత్ర కు సమయంలో అదే మొత్తం పడుతుంది.
మీరు అక్షరాలు సంఖ్య పెంచడానికి, వంటి
runtime ఇన్పుట్ పొడవు సరళంగా పెరుగుతుంది.
>> మీరు ఆ సరళ సమయం నిర్ణయించుకుంటే ఇప్పుడు, ఊహించుకోండి
O (n), కేవలం తగినంత వేగం మీరు కాదు?
బహుశా మీరు, భారీ తీగలను నిల్వ చేసిన
మరియు మీరు పడుతుంది అదనపు సమయంలో భరించలేని
ఒకటి తరువాత ఒకటి లెక్కింపు వారి అక్షరాలు అన్ని దాటటానికి.
కాబట్టి, మీరు ప్రయత్నించాలనుకుంటే నిర్ణయించుకుంటారు.
మీరు ఇప్పటికే అక్షరాలు సంఖ్య నిల్వ జరుగుతుంది ఉంటే
స్ట్రింగ్ లో, ', లెన్' అనే వేరియబుల్ సే,
ప్రారంభ కార్యక్రమం లో,
మీరు కూడా మీ స్ట్రింగ్ లో మొట్టమొదటి పాత్ర నిల్వ ముందు?
అప్పుడు, అన్ని మీరు, స్ట్రింగ్ పొడవు కనుగొనేందుకు ఇప్పుడు లేదు భావిస్తున్న
వేరియబుల్ యొక్క విలువ ఏమిటి తనిఖీ ఉంది.
మీరు అన్ని వద్ద స్ట్రింగ్ కూడా చూడండి ఉండదనే
మరియు లెన్ వంటి వేరియబుల్ విలువ యాక్సెస్ భావిస్తారు
ఒక asymptotically స్థిరంగా సమయం ఆపరేషన్,
లేదా O (1).
ఎందుకు ఉంది? Well, asymptotic సంక్లిష్టత అర్థం గుర్తు.
ఎలా పరిమాణం runtime మార్పు చేస్తుంది
మీ ఇన్పుట్లను పెరుగుతుంది?
>> మీరు ఒక పెద్ద స్ట్రింగ్ లో అక్షరాలు సంఖ్యను పొందడం ప్రయత్నిస్తున్న సే.
సరే,, మీరు తీగ ఎలా పెద్ద పట్టింపు లేదు
ఒక మిలియన్ అక్షరాల పొడవు,
అన్ని మీరు, ఈ పద్ధతిలో ఉన్న స్ట్రింగ్ యొక్క పొడవు కనుగొనేందుకు చేయడానికి భావిస్తాను
, వేరియబుల్ లెన్ యొక్క విలువ చదివి ఉంది
మీరు ఇప్పటికే చేసింది.
అని ఇన్పుట్ పొడవు, మీరు కనుగొనేందుకు ప్రయత్నిస్తున్న స్ట్రింగ్ యొక్క పొడవు,
మీ కార్యక్రమం నడుపుతుంది ఎంత వేగంగా అన్ని వద్ద ప్రభావితం చేయదు.
మీ ప్రోగ్రామ్ యొక్క ఈ భాగం ఒక పాత్ర స్ట్రింగ్ న సమానంగా ఫాస్ట్ అమలు
మరియు ఒక వేయి పాత్ర స్ట్రింగ్,
ఈ కార్యక్రమం నిరంతరం సమయంలో అమలు సూచిస్తారు ఎందుకు మరియు ఆ
ఇన్పుట్ పరిమాణం సంబంధించి.
>> అయితే, ఒక ప్రతికూలతగా లేదు.
మీరు మీ కంప్యూటర్ లో అదనపు మెమరీని ఖర్చు
వేరియబుల్ నిల్వ
మరియు మీరు పడుతుంది అదనపు సమయం
వేరియబుల్ యొక్క నిజమైన నిల్వ చేయడానికి,
కానీ పాయింట్ ఇప్పటికీ నిలిచి,
మీ స్ట్రింగ్ ఉంది ఎంత కాలం కనుగొనడంలో
అన్ని వద్ద స్ట్రింగ్ యొక్క పొడవు మీద ఆధారపడి ఉండదు.
కాబట్టి, అది ఓ (1) లేదా స్థిరమైన సమయంలో నడుస్తుంది.
ఈ ఖచ్చితంగా అర్థం లేదు
మీ కోడ్, 1 స్టెప్ లో నడిపే
కానీ ఎంత అనేక దశలు ఇది,
అది ఇన్పుట్లను పరిమాణం తో మారకపోతే,
అది ఇప్పటికీ మేము O (1) వంటి ఇది asymptotically స్థిరంగా ఉంది.
>> మీరు బహుశా అంచనా వంటి,
క్రమసూత్ర పద్ధతులు కొలిచేందుకు అనేక పెద్ద O runtimes ఉన్నాయి.
O (n) ² అల్గోరిథంలు O (n) అల్గోరిథంలు కంటే asymptotically నెమ్మదిగా ఉంటాయి.
మూలకాల సంఖ్య (n) వృధ్ధి ఆ, ఉంది
చివరికి ఓ (n) ² అల్గోరిథంలు ఎక్కువ సమయం పడుతుంది
O (n) అల్గోరిథంలు అమలు కంటే.
ఈ O (n) అల్గోరిథంలు ఎల్లప్పుడూ వేగంగా అమలు కాదు
O (n) ² అల్గోరిథంలు కంటే, ఒకే వాతావరణంలో,
అదే హార్డువేరు మీద.
బహుశా చిన్న ఇన్పుట్ పరిమాణాల్లో,
O (n) ² క్రమసూత్ర పద్ధతి నిజానికి, వేగంగా పని ఉండవచ్చు
కానీ, చివరికి, ఇన్పుట్ పరిమాణం పెరుగుతుంది
అనంతం వైపు, O (n) ² అల్గోరిథం యొక్క రన్టైమ్
చివరికి ఓ (n) అల్గోరిథం యొక్క రన్టైమ్ మరుగు చేసినా కనిపిస్తుంది.
ఏ వర్గ గణిత ఫంక్షన్ వంటి
చివరికి ఏ సరళ ఫంక్షన్ అధిగమిస్తుందనే కనిపిస్తుంది,
ఎంత తల యొక్క సరళ ఫంక్షన్ మొదలు ఉన్నా తో మొదలవుతుంది.
మీరు డేటా పెద్ద మొత్తంలో పని చేస్తే
O అమలు ఆ అల్గోరిథంలు (n) ² సమయం నిజంగా, మీ ప్రోగ్రామ్ నెమ్మదిగా పని అవుతుంది
కానీ చిన్న ఇన్పుట్ పరిమాణాల్లో,
మీరు బహుశా గమనించి కూడా లేదు.
>> మరో asymptotic సంక్లిష్టత ఉంటుంది
సంవర్గమాన సమయం, O (n లాగ్).
త్వరగా ఈ నడిపే ఒక అల్గోరిథం యొక్క ఒక ఉదాహరణ
, క్లాసిక్ బైనరీ శోధన అల్గోరిథం
అంశాల ఇప్పటికే క్రమబద్ధీకరించబడతాయి జాబితాలో ఒక మూలకం కనుగొనడానికి.
>> మీరు బైనరీ శోధన ఏమి తెలియకపోతే,
నేను నిజంగా త్వరగా మీ కోసం వివరించడానికి చేస్తాము.
మీరు సంఖ్య 3 చూస్తున్న సే
పూర్ణాంకాల ఈ శ్రేణి లో.
ఇది అర్రే మధ్య మూలకం వద్ద ఉంది
మరియు "నేను కంటే ఎక్కువ కావలసిన ఎలిమెంట్ సమానంగా లేదా ఈ కంటే తక్కువ?" అని అడుగుతాడు
అది గొప్ప, సమాన అయితే. మీరు మూలకం కనుగొనబడింది, మరియు మీరు పూర్తి చేసిన.
ఇది అధిక అది మీరు మూలకం తెలుసు
, అర్రే యొక్క కుడివైపు ఉండాలి
మరియు మీరు మాత్రమే, భవిష్యత్తులో ఆ చూడవచ్చు
చిన్న అయితే మరియు, అప్పుడు మీరు ఎడమ వైపు ఉండాలి తెలుసు.
ఈ ప్రక్రియ తర్వాత చిన్న పరిమాణ శ్రేణి తిరిగి చేయబడుతుంది
సరైన మూలకం కనిపించే వరకు.
>> ఈ శక్తివంతమైన అల్గోరిథం ప్రతి చర్య సగానికి అర్రే పరిమాణం తగ్గిస్తుంది.
కాబట్టి, పరిమాణం 8 ఒక క్రమబద్ధీకరించబడతాయి శ్రేణి ఒక మూలకం కనుగొనేందుకు,
అత్యంత వద్ద (₂ 8 లాగిన్),
ఈ ఆపరేషన్లలో లేదా 3,
మధ్య మూలకం తనిఖీ, అప్పుడు సగం లో అర్రే కత్తిరించి, అవసరం
పరిమాణం 16 యొక్క వ్యూహం, (₂ 16 లాగ్) చేపట్టింది
లేదా 4 కార్యకలాపాలు.
మాత్రమే ఒక రెట్టింపు పరిమాణంలో శ్రేణి కోసం 1 మరింత ఆపరేషన్ ఉంది.
అర్రే పరిమాణం రెట్టింపు
ఈ కోడ్ యొక్క మాత్రమే 1 భాగం ద్వారా runtime పెంచుతుంది.
మళ్లీ, అప్పుడు విభజన, జాబితా మధ్య మూలకం తనిఖీ.
కాబట్టి, అది, సంవర్గమాన సమయంలో ఆపరేట్ చెప్పబడింది
O (n లాగ్).
కానీ, మీరు చెప్పిన వేచి
జాబితాలో మీరు చూస్తున్న మూలకం ఉన్న ఈ ఆధారపడి ఉండదు?
ఏం మీరు చూడండి మొదటి మూలకం కుడి ఒకటిగా జరుగుతుంది?
అప్పుడు మాత్రమే, 1 ఆపరేషన్ పడుతుంది
జాబితా ఎంత పెద్ద ఉన్నా.
>> కంప్యూటర్ శాస్త్రవేత్తలు మరింత నిబంధనలు ఎందుకు సరే, ఆ
ఉత్తమ కేసు ప్రతిబింబించే asymptotic క్లిష్టతకు
మరియు అతి దారుణమైన విషయం ఒక అల్గోరిథం యొక్క ప్రదర్శనలు.
సరిగా ఎగువ మరియు దిగువ హద్దులు
runtime లో.
బైనరీ శోధన ఉత్తమ సందర్భంలో, మా అంశం
అక్కడే మధ్యలో,
మరియు మీరు, స్థిరమైన సమయంలో అది పొందండి
అర్రే మిగిలిన ఎలా పెద్దది ఉన్నా.
ఈ కోసం ఉపయోగిస్తారు Ω ఉంది.
కాబట్టి, ఈ అల్గోరిథం Ω (1) అమలు చెబుతారు.
ఉత్తమ సందర్భంలో, ఇది త్వరగా మూలకం తెలుసుకుంటాడు
శ్రేణి ఎంత పెద్ద ఉన్నా,
కానీ విషయంలో లో,
అది (లాగ్ n) స్ప్లిట్ తనిఖీలను ఉంటుంది
యెరే యొక్క కుడి మూలకం కనుగొనేందుకు.
చెత్త-సందర్భంలో ఎగువ హద్దులు మీరు ఇప్పటికే తెలిసిన పెద్ద "O" తో సూచిస్తారు.
కాబట్టి, అది O (n లాగ్), కానీ Ω (1) ఉంది.
>> ఒక సరళ శోధన దీనికి విరుద్ధంగా,
మీరు శ్రేణి యొక్క ప్రతి మూలకం నడవడానికి దీనిలో
మీకు కావలసిన ఒక కనుగొనడానికి,
ఉత్తమ Ω (1) ఉంది.
మళ్లీ, మొదటి మూలకం మీరు.
కాబట్టి, అది యెరే ఎంత పెద్ద పట్టింపు లేదు.
చెత్త సందర్భంలో, అది యెరే నందలి చివరి ఎలిమెంట్.
కాబట్టి, మీరు, దానిని కనుగొనేందుకు శ్రేణి అన్ని n మూలకాలు నడవడానికి కలిగి
మీరు ఒక 3 వెతుకుతున్న ఉంటే ఇష్టం.
కాబట్టి, అది O (n) సమయంలో నడుస్తుంది
అది యెరే నందలి మూలకాల సంఖ్య నిష్పత్తిలో ఎందుకంటే.
>> ఉపయోగించే ఒక మరింత గుర్తు Θ ఉంది.
ఈ పేరు ఉత్తమ మరియు చెత్త కేసులు అల్గోరిథంలు వివరించడానికి ఉపయోగిస్తారు
ఒకే విధంగా ఉంటాయి.
ఈ మేము ముందుగా గురించి మాట్లాడారు స్ట్రింగ్ నిడివి అల్గోరిథంలు వర్తిస్తుంది.
మేము ముందు ఒక వేరియబుల్ నిల్వ ఉంటే అంటే,
మేము స్ట్రింగ్ నిల్వ మరియు తరువాత స్థిరంగా సమయంలో అది యాక్సెస్.
ఏ సంఖ్య ఉన్నా
మేము ఆ వేరియబుల్ నిల్వ చేస్తున్నాము, మేము ఇది చూడండి ఉంటుంది.
ఉత్తమ సందర్భంలో, మేము ఇది చూడండి
మరియు స్ట్రింగ్ యొక్క పొడవు కనుగొనండి.
Ω (1) లేదా ఉత్తమ కేసు స్థిరంగా సమయంలో.
విషయంలో, ఉంది
మేము దాన్ని చూసి స్ట్రింగ్ యొక్క పొడవు కనుగొనండి.
కాబట్టి, ఓ (1) లేదా విషయంలో నిరంతరం సమయం.
కాబట్టి, ఉత్తమ కేసు మరియు చెత్త కేసులు నుండి ఒకటే
ఈ Θ (1) సమయంలో అమలు చెప్పవచ్చు.
>> సారాంశంలో, మేము సంకేతాలు సామర్ధ్యాన్ని కారణం మంచి మార్గాలు ఉన్నాయి
వారు అమలు చేయడానికి తీసుకుని వాస్తవ ప్రపంచ సమయం గురించి ఏదైనా తెలియకుండా,
ఇది బయట కారకాలు మా ప్రభావితమవుతుంది
వేర్వేరు హార్డ్వేర్, సాఫ్ట్వేర్, సహా
లేదా మీ కోడ్ ప్రత్యేకతలు.
అలాగే, ఇది మాకు ఏం జరుగుతుందో గురించి బాగా కారణం అనుమతిస్తుంది
ఉన్నప్పుడు ఇన్పుట్లను పెరుగుతుంది పరిమాణం.
>> మీరు O (n) ² అల్గోరిథం, అమలు చేస్తే
లేదా మరింత, ఒక O (2 ⁿ) అల్గోరిథం,
వేగంగా పెరుగుతున్న రకాల్లో ఒకటి
మీరు నిజంగా మందగింపు గమనించి ప్రారంభించగలరు
మీరు డేటా పెద్ద మొత్తంలో పని ప్రారంభించండి.
>> ఆ asymptotic సంక్లిష్టత ఉంటుంది. ధన్యవాదాలు.