అల్గోరిథమిక్ సంక్లిష్టత

హాయ్! ఈ రోజు పాఠం మిగిలిన వాటి నుండి కొద్దిగా భిన్నంగా ఉంటుంది. ఇది జావాకు పరోక్షంగా మాత్రమే సంబంధించినది కాబట్టి ఇది భిన్నంగా ఉంటుంది. ప్రతి ప్రోగ్రామర్‌కు ఈ అంశం చాలా ముఖ్యమైనదని పేర్కొంది. మేము అల్గారిథమ్‌ల గురించి మాట్లాడబోతున్నాము . అల్గోరిథం అంటే ఏమిటి? సరళంగా చెప్పాలంటే, ఇది ఆశించిన ఫలితాన్ని సాధించడానికి పూర్తి చేయవలసిన కొన్ని చర్యల క్రమం . మేము రోజువారీ జీవితంలో తరచుగా అల్గారిథమ్‌లను ఉపయోగిస్తాము. ఉదాహరణకు, ప్రతి ఉదయం మీకు ఒక నిర్దిష్ట పని ఉంటుంది: పాఠశాలకు లేదా పనికి వెళ్లండి మరియు అదే సమయంలో:

• దుస్తులు ధరించారు
• శుభ్రంగా
• ఫెడ్

ఈ ఫలితాన్ని సాధించడానికి మిమ్మల్ని ఏ అల్గోరిథం అనుమతిస్తుంది?

1. అలారం గడియారాన్ని ఉపయోగించి మేల్కొలపండి.
2. స్నానం చేసి మీరే కడగాలి.
3. అల్పాహారం మరియు కొంచెం కాఫీ లేదా టీ చేయండి.
4. తినండి.
5. మీరు ముందు రోజు సాయంత్రం మీ బట్టలు ఇస్త్రీ చేయకపోతే, వాటిని ఇస్త్రీ చేయండి.
6. వస్త్ర దారణ.
7. ఇల్లు వదలి వెళ్ళండి.

ఈ చర్యల క్రమం ఖచ్చితంగా మీరు ఆశించిన ఫలితాన్ని పొందేలా చేస్తుంది. ప్రోగ్రామింగ్‌లో, మేము పనులను పూర్తి చేయడానికి నిరంతరం కృషి చేస్తాము. ఈ పనులలో గణనీయమైన భాగాన్ని ఇప్పటికే తెలిసిన అల్గారిథమ్‌లను ఉపయోగించి నిర్వహించవచ్చు. ఉదాహరణకు, మీ పని ఇది అని అనుకుందాం: ఒక శ్రేణిలో 100 పేర్ల జాబితాను క్రమబద్ధీకరించండి . ఈ పని చాలా సులభం, కానీ ఇది వివిధ మార్గాల్లో పరిష్కరించబడుతుంది. ఇక్కడ ఒక సాధ్యమైన పరిష్కారం ఉంది: పేర్లను అక్షర క్రమంలో క్రమబద్ధీకరించడానికి అల్గోరిథం:

1. వెబ్‌స్టర్స్ థర్డ్ న్యూ ఇంటర్నేషనల్ డిక్షనరీ యొక్క 1961 ఎడిషన్‌ను కొనుగోలు చేయండి లేదా డౌన్‌లోడ్ చేయండి.
2. ఈ నిఘంటువులో మా జాబితా నుండి ప్రతి పేరును కనుగొనండి.
3. ఒక కాగితంపై, పేరు ఉన్న నిఘంటువు పేజీని వ్రాయండి.
4. పేర్లను క్రమబద్ధీకరించడానికి కాగితపు ముక్కలను ఉపయోగించండి.

అటువంటి చర్యల క్రమం మన పనిని సాధిస్తుందా? అవును, అది ఖచ్చితంగా అవుతుంది. ఈ పరిష్కారం సమర్థవంతమైనదా ? కష్టంగా. ఇక్కడ మేము అల్గారిథమ్‌ల యొక్క మరొక ముఖ్యమైన అంశాలకు వచ్చాము: వాటి సామర్థ్యం . ఈ పనిని సాధించడానికి అనేక మార్గాలు ఉన్నాయి. కానీ ప్రోగ్రామింగ్‌లో మరియు సాధారణ జీవితంలో, మేము అత్యంత సమర్థవంతమైన మార్గాన్ని ఎంచుకోవాలనుకుంటున్నాము. మీ పని టోస్ట్ యొక్క వెన్నతో కూడిన ముక్కను తయారు చేయడం అయితే, మీరు గోధుమలను విత్తడం మరియు ఆవు పాలు పితకడం ద్వారా ప్రారంభించవచ్చు. కానీ అది అసమర్థంగా ఉంటుందిపరిష్కారం - ఇది చాలా సమయం పడుతుంది మరియు చాలా డబ్బు ఖర్చు అవుతుంది. మీరు కేవలం బ్రెడ్ మరియు వెన్న కొనుగోలు చేయడం ద్వారా మీ సాధారణ పనిని సాధించవచ్చు. సమస్యను పరిష్కరించడానికి ఇది మిమ్మల్ని అనుమతించినప్పటికీ, గోధుమ మరియు ఆవుతో కూడిన అల్గోరిథం ఆచరణలో ఉపయోగించడానికి చాలా క్లిష్టంగా ఉంటుంది. ప్రోగ్రామింగ్‌లో, అల్గారిథమ్‌ల సంక్లిష్టతను అంచనా వేయడానికి పెద్ద O సంజ్ఞామానం అనే ప్రత్యేక సంజ్ఞామానం మాకు ఉంది. ఇన్‌పుట్ డేటా పరిమాణంపై అల్గారిథమ్ అమలు సమయం ఎంత ఆధారపడి ఉంటుందో అంచనా వేయడాన్ని బిగ్ O సాధ్యం చేస్తుంది . సరళమైన ఉదాహరణను చూద్దాం: డేటా బదిలీ. మీరు చాలా దూరం (ఉదాహరణకు, 5000 మైళ్ళు) ఫైల్ రూపంలో కొంత సమాచారాన్ని పంపవలసి ఉంటుందని ఊహించండి. ఏ అల్గోరిథం అత్యంత ప్రభావవంతంగా ఉంటుంది? ఇది మీరు పని చేస్తున్న డేటాపై ఆధారపడి ఉంటుంది. ఉదాహరణకు, మనకు 10 MB ఆడియో ఫైల్ ఉందని అనుకుందాం. ఈ సందర్భంలో, ఇంటర్నెట్ ద్వారా ఫైల్‌ను పంపడం అత్యంత సమర్థవంతమైన అల్గోరిథం. దీనికి రెండు నిమిషాల కంటే ఎక్కువ సమయం పట్టదు! మన అల్గారిథమ్‌ను పునరుద్ఘాటిద్దాం: "మీరు 5000 మైళ్ల దూరంలో ఉన్న ఫైల్‌ల రూపంలో సమాచారాన్ని బదిలీ చేయాలనుకుంటే, మీరు ఇంటర్నెట్ ద్వారా డేటాను పంపాలి". అద్భుతమైన. ఇప్పుడు దానిని విశ్లేషిద్దాం. ఇది మన పనిని పూర్తి చేస్తుందా?బాగా, అవును, అది చేస్తుంది. కానీ దాని సంక్లిష్టత గురించి మనం ఏమి చెప్పగలం? అయ్యో, ఇప్పుడు విషయాలు మరింత ఆసక్తికరంగా మారుతున్నాయి. వాస్తవం ఏమిటంటే, మా అల్గోరిథం ఇన్‌పుట్ డేటాపై ఆధారపడి ఉంటుంది, అవి ఫైల్‌ల పరిమాణం. మనకు 10 మెగాబైట్‌లు ఉంటే, అప్పుడు అంతా బాగానే ఉంటుంది. అయితే మనం 500 మెగాబైట్లను పంపవలసి వస్తే? 20 గిగాబైట్లు? 500 టెరాబైట్లు? 30 పెటాబైట్‌లు? మా అల్గోరిథం పని చేయడం ఆగిపోతుందా? లేదు, ఈ మొత్తం డేటా మొత్తం బదిలీ చేయబడుతుంది. ఇంకెంత కాలం పడుతుందో? అవును, అది అవుతుంది! ఇప్పుడు మా అల్గారిథమ్‌లోని ఒక ముఖ్యమైన లక్షణం మనకు తెలుసు: పెద్ద మొత్తంలో డేటా పంపబడుతుంది, అల్గారిథమ్‌ను అమలు చేయడానికి ఎక్కువ సమయం పడుతుంది.. కానీ మేము ఈ సంబంధం గురించి మరింత ఖచ్చితమైన అవగాహన కలిగి ఉండాలనుకుంటున్నాము (ఇన్‌పుట్ డేటా పరిమాణం మరియు దానిని పంపడానికి అవసరమైన సమయం మధ్య). మా విషయంలో, అల్గోరిథమిక్ సంక్లిష్టత సరళంగా ఉంటుంది . "లీనియర్" అంటే ఇన్‌పుట్ డేటా మొత్తం పెరిగేకొద్దీ, దానిని పంపడానికి పట్టే సమయం దాదాపు దామాషా ప్రకారం పెరుగుతుంది. డేటా మొత్తం రెట్టింపు అయితే, దానిని పంపడానికి అవసరమైన సమయం రెండు రెట్లు ఎక్కువ అవుతుంది. డేటా 10 రెట్లు పెరిగితే, ప్రసార సమయం 10 రెట్లు పెరుగుతుంది. పెద్ద O సంజ్ఞామానాన్ని ఉపయోగించి, మా అల్గోరిథం యొక్క సంక్లిష్టత O(n) గా వ్యక్తీకరించబడుతుంది. మీరు భవిష్యత్తు కోసం ఈ సంజ్ఞామానాన్ని గుర్తుంచుకోవాలి - ఇది ఎల్లప్పుడూ సరళ సంక్లిష్టతతో అల్గారిథమ్‌ల కోసం ఉపయోగించబడుతుంది. మేము ఇక్కడ మారే అనేక విషయాల గురించి మాట్లాడటం లేదని గమనించండి: ఇంటర్నెట్ వేగం, మా కంప్యూటర్ యొక్క గణన శక్తి మరియు మొదలైనవి. అల్గోరిథం యొక్క సంక్లిష్టతను అంచనా వేసేటప్పుడు, ఈ కారకాలను పరిగణనలోకి తీసుకోవడం సమంజసం కాదు - ఏదైనా సందర్భంలో, అవి మన నియంత్రణలో లేవు. బిగ్ O సంజ్ఞామానం అల్గోరిథం యొక్క సంక్లిష్టతను వ్యక్తపరుస్తుంది, అది అమలు చేసే "పర్యావరణం" కాదు. మన ఉదాహరణతో కొనసాగిద్దాం. మనం 800 టెరాబైట్‌ల ఫైళ్లను పంపాలని చివరికి తెలుసుకున్నామని అనుకుందాం. మేము వాటిని ఇంటర్నెట్ ద్వారా పంపడం ద్వారా మా పనిని పూర్తి చేయగలము. కేవలం ఒక సమస్య మాత్రమే ఉంది: ప్రామాణిక గృహ డేటా ప్రసార రేట్లు (సెకనుకు 100 మెగాబిట్లు), దీనికి సుమారు 708 రోజులు పడుతుంది. దాదాపు 2 సంవత్సరాలు! :O మా అల్గోరిథం ఇక్కడ సరిగ్గా సరిపోదు. మాకు వేరే పరిష్కారం కావాలి! ఊహించని రీతిలో ఐటీ దిగ్గజం అమెజాన్‌ మనల్ని రక్షించింది! Amazon యొక్క స్నోమొబైల్ సేవ పెద్ద మొత్తంలో డేటాను మొబైల్ నిల్వకు అప్‌లోడ్ చేసి, ఆపై దానిని ట్రక్ ద్వారా కావలసిన చిరునామాకు బట్వాడా చేస్తుంది! కాబట్టి, మాకు కొత్త అల్గోరిథం ఉంది! "మీరు 5000 మైళ్ల దూరంలో ఉన్న సమాచారాన్ని ఫైల్‌ల రూపంలో బదిలీ చేయాలనుకుంటే మరియు ఇంటర్నెట్ ద్వారా పంపడానికి 14 రోజుల కంటే ఎక్కువ సమయం తీసుకుంటే, మీరు డేటాను అమెజాన్ ట్రక్కులో పంపాలి." మేము ఇక్కడ ఏకపక్షంగా 14 రోజులను ఎంచుకున్నాము. ఇది మనం వేచి ఉండగల సుదీర్ఘ కాలం అని చెప్పండి. మన అల్గోరిథంను విశ్లేషిద్దాం. దాని వేగం గురించి ఏమిటి? ట్రక్ కేవలం 50 mph వేగంతో ప్రయాణించినప్పటికీ, అది కేవలం 100 గంటల్లో 5000 మైళ్లను కవర్ చేస్తుంది. ఇది నాలుగు రోజుల కంటే కొంచెం ఎక్కువ! ఇంటర్నెట్ ద్వారా డేటాను పంపే ఎంపిక కంటే ఇది చాలా ఉత్తమం. మరియు ఈ అల్గోరిథం యొక్క సంక్లిష్టత గురించి ఏమిటి? ఇది కూడా సరళంగా ఉందా, అంటే O(n)? కాదు, అదికాదు. అన్నింటికంటే, మీరు దానిని ఎంత భారీగా లోడ్ చేస్తున్నారో ట్రక్కు పట్టించుకోదు - ఇది ఇప్పటికీ అదే వేగంతో డ్రైవ్ చేస్తుంది మరియు సమయానికి చేరుకుంటుంది. మన దగ్గర 800 టెరాబైట్‌లు ఉన్నా, లేదా దానికి 10 రెట్లు ఉన్నా, ట్రక్ 5 రోజులలోపు గమ్యస్థానానికి చేరుకుంటుంది. మరో మాటలో చెప్పాలంటే, ట్రక్ ఆధారిత డేటా బదిలీ అల్గోరిథం స్థిరమైన సంక్లిష్టతను కలిగి ఉంటుంది. ఇక్కడ, "స్థిరం" అంటే ఇది ఇన్‌పుట్ డేటా పరిమాణంపై ఆధారపడి ఉండదు. ట్రక్కులో 1GB ఫ్లాష్ డ్రైవ్ ఉంచండి, అది 5 రోజుల్లో వస్తుంది. 800 టెరాబైట్ల డేటా ఉన్న డిస్క్‌లలో ఉంచండి, అది 5 రోజుల్లో వస్తుంది. పెద్ద O సంజ్ఞామానాన్ని ఉపయోగిస్తున్నప్పుడు, స్థిరమైన సంక్లిష్టత O(1) ద్వారా సూచించబడుతుంది . మేము O(n) మరియు O(1) లతో సుపరిచితులు అయ్యాము , కాబట్టి ఇప్పుడు ప్రోగ్రామింగ్ ప్రపంచంలోని మరిన్ని ఉదాహరణలను చూద్దాం :) మీకు 100 సంఖ్యల శ్రేణిని అందించారని అనుకుందాం మరియు వాటిలో ప్రతి ఒక్కటి ప్రదర్శించడం పని. కన్సోల్. forమీరు ఈ పనిని నిర్వహించే సాధారణ లూప్‌ను వ్రాస్తారు

int[] numbers = new int[100];
// ...fill the array with numbers

for (int i: numbers) {
   System.out.println(i);
}

ఈ అల్గోరిథం యొక్క సంక్లిష్టత ఏమిటి? లీనియర్, అనగా O(n). ప్రోగ్రామ్ తప్పనిసరిగా నిర్వహించాల్సిన చర్యల సంఖ్య దానికి ఎన్ని సంఖ్యలు పంపబడిందనే దానిపై ఆధారపడి ఉంటుంది. శ్రేణిలో 100 సంఖ్యలు ఉంటే, 100 చర్యలు ఉంటాయి (స్క్రీన్‌పై స్ట్రింగ్‌లను ప్రదర్శించడానికి స్టేట్‌మెంట్‌లు). శ్రేణిలో 10,000 సంఖ్యలు ఉంటే, 10,000 చర్యలు తప్పనిసరిగా చేయాలి. మన అల్గారిథమ్‌ను ఏ విధంగానైనా మెరుగుపరచవచ్చా? లేదు. ఏది ఏమైనప్పటికీ, కన్సోల్‌లో స్ట్రింగ్‌లను ప్రదర్శించడానికి మేము శ్రేణి ద్వారా N పాస్‌లను చేయాలి మరియు N స్టేట్‌మెంట్‌లను అమలు చేయాలి. మరొక ఉదాహరణను పరిగణించండి.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

LinkedListమేము అనేక సంఖ్యలను చొప్పించే ఖాళీని కలిగి ఉన్నాము . LinkedListమా ఉదాహరణలో ఒకే సంఖ్యను ఇన్‌సర్ట్ చేసే అల్గారిథమిక్ సంక్లిష్టతను మరియు జాబితాలోని మూలకాల సంఖ్యపై అది ఎలా ఆధారపడి ఉంటుందో మనం విశ్లేషించాలి . సమాధానం O(1), అనగా స్థిరమైన సంక్లిష్టత . ఎందుకు? మేము జాబితా ప్రారంభంలో ప్రతి సంఖ్యను చొప్పించామని గమనించండి. LinkedListఅదనంగా, మీరు సంఖ్యను a లోకి చొప్పించినప్పుడు , మూలకాలు ఎక్కడికీ కదలవని మీరు గుర్తుచేసుకుంటారు . లింక్‌లు (లేదా సూచనలు) అప్‌డేట్ చేయబడ్డాయి (లింక్డ్‌లిస్ట్ ఎలా పనిచేస్తుందో మీరు మర్చిపోయినట్లయితే, మా పాత పాఠాల్లో ఒకదానిని చూడండి ). మన జాబితాలో మొదటి సంఖ్య x, మరియు మేము జాబితా ముందు భాగంలో y సంఖ్యను చొప్పించినట్లయితే, మనం చేయాల్సిందల్లా:

x.previous  = y;
y.previous = null;
y.next = x;

మేము లింక్‌లను అప్‌డేట్ చేసినప్పుడు, ఒకటి లేదా ఒక బిలియన్‌లో ఇప్పటికే ఎన్ని నంబర్‌లు ఉన్నాయో మేము పట్టించుకోముLinkedList . అల్గోరిథం యొక్క సంక్లిష్టత స్థిరంగా ఉంటుంది, అనగా O(1).

లాగరిథమిక్ సంక్లిష్టత

ఆందోళన పడకండి! :) "లాగరిథమిక్" అనే పదం మీరు ఈ పాఠాన్ని ముగించి, చదవడం ఆపివేయాలనిపిస్తే, రెండు నిమిషాలు పట్టుకోండి. ఇక్కడ ఎటువంటి క్రేజీ గణితం ఉండదు (ఇలాంటి వివరణలు చాలా చోట్ల ఉన్నాయి), మరియు మేము ప్రతి ఉదాహరణను వేరుగా ఎంచుకుంటాము. 100 సంఖ్యల శ్రేణిలో ఒక నిర్దిష్ట సంఖ్యను కనుగొనడం మీ పని అని ఊహించండి. మరింత ఖచ్చితంగా, మీరు అక్కడ ఉందో లేదో తనిఖీ చేయాలి. అవసరమైన సంఖ్య కనుగొనబడిన వెంటనే, శోధన ముగుస్తుంది మరియు మీరు కన్సోల్‌లో క్రింది వాటిని ప్రదర్శిస్తారు: "అవసరమైన సంఖ్య కనుగొనబడింది! శ్రేణిలో దాని సూచిక = ...." మీరు ఈ పనిని ఎలా పూర్తి చేస్తారు? ఇక్కడ పరిష్కారం స్పష్టంగా ఉంది: మీరు మొదటి నుండి (లేదా చివరి నుండి) ప్రారంభించి, శ్రేణిలోని మూలకాలను ఒక్కొక్కటిగా పునరావృతం చేయాలి మరియు ప్రస్తుత సంఖ్య మీరు వెతుకుతున్న దానికి సరిపోతుందో లేదో తనిఖీ చేయాలి. దీని ప్రకారం, చర్యల సంఖ్య నేరుగా శ్రేణిలోని మూలకాల సంఖ్యపై ఆధారపడి ఉంటుంది. మనకు 100 సంఖ్యలు ఉన్నట్లయితే, మనం తదుపరి మూలకానికి 100 సార్లు వెళ్లి 100 పోలికలను నిర్వహించవలసి ఉంటుంది. 1000 సంఖ్యలు ఉంటే, అప్పుడు 1000 పోలికలు ఉండవచ్చు. ఇది స్పష్టంగా సరళ సంక్లిష్టత, అనగాO(n) . ఇప్పుడు మేము మా ఉదాహరణకి ఒక శుద్ధీకరణను జోడిస్తాము: మీరు సంఖ్యను కనుగొనవలసిన శ్రేణి ఆరోహణ క్రమంలో క్రమబద్ధీకరించబడుతుంది . ఇది మన విధికి సంబంధించి ఏదైనా మారుతుందా? మేము ఇప్పటికీ కావలసిన సంఖ్య కోసం బ్రూట్-ఫోర్స్ శోధనను నిర్వహించగలము. కానీ ప్రత్యామ్నాయంగా, మనం బాగా తెలిసిన బైనరీ శోధన అల్గారిథమ్‌ని ఉపయోగించవచ్చు . చిత్రంలో ఎగువ వరుసలో, మేము క్రమబద్ధీకరించబడిన శ్రేణిని చూస్తాము. అందులో 23 సంఖ్యను కనుక్కోవాలి. సంఖ్యలపై మళ్లించే బదులు, మేము శ్రేణిని 2 భాగాలుగా విభజించి, శ్రేణిలోని మధ్య సంఖ్యను తనిఖీ చేస్తాము. సెల్ 4లో ఉన్న సంఖ్యను కనుగొని దాన్ని తనిఖీ చేయండి (చిత్రంలో రెండవ వరుస). ఈ సంఖ్య 16, మరియు మేము 23 కోసం చూస్తున్నాము. ప్రస్తుత సంఖ్య మనం వెతుకుతున్న దాని కంటే తక్కువగా ఉంది. అంటే ఏమిటి? దాని అర్థం ఏమిటంటేఅన్ని మునుపటి సంఖ్యలు (సంఖ్య 16 కంటే ముందు ఉన్నవి) తనిఖీ చేయవలసిన అవసరం లేదు : అవి మనం వెతుకుతున్న దాని కంటే తక్కువగా ఉంటాయని హామీ ఇవ్వబడింది, ఎందుకంటే మా శ్రేణి క్రమబద్ధీకరించబడింది! మేము మిగిలిన 5 అంశాలలో శోధనను కొనసాగిస్తాము. గమనిక:మేము కేవలం ఒక పోలికను మాత్రమే ప్రదర్శించాము, కానీ మేము ఇప్పటికే సాధ్యమయ్యే ఎంపికలలో సగాన్ని తొలగించాము. మాకు 5 అంశాలు మాత్రమే మిగిలి ఉన్నాయి. మిగిలిన సబ్‌రేను సగానికి విభజించి, మళ్లీ మధ్య మూలకాన్ని (చిత్రంలో 3వ వరుస) తీసుకోవడం ద్వారా మేము మా మునుపటి దశను పునరావృతం చేస్తాము. సంఖ్య 56, మరియు ఇది మనం వెతుకుతున్న దాని కంటే పెద్దది. అంటే ఏమిటి? మేము మరో 3 అవకాశాలను తొలగించామని దీని అర్థం: సంఖ్య 56 అలాగే దాని తర్వాత ఉన్న రెండు సంఖ్యలు (అవి 23 కంటే ఎక్కువగా ఉన్నాయని హామీ ఇవ్వబడినందున, శ్రేణి క్రమబద్ధీకరించబడింది). తనిఖీ చేయడానికి మాకు 2 సంఖ్యలు మాత్రమే మిగిలి ఉన్నాయి (చిత్రంలో చివరి వరుస) — శ్రేణి సూచికలు 5 మరియు 6తో ఉన్న సంఖ్యలు. మేము వాటిలో మొదటిదాన్ని తనిఖీ చేసి, మేము వెతుకుతున్న దాన్ని కనుగొంటాము — సంఖ్య 23! దీని సూచిక 5! మన అల్గోరిథం ఫలితాలను చూద్దాం, ఆపై మనం' దాని సంక్లిష్టతను విశ్లేషిస్తాను. మార్గం ద్వారా, దీన్ని బైనరీ శోధన అని ఎందుకు పిలుస్తారో ఇప్పుడు మీరు అర్థం చేసుకున్నారు: ఇది డేటాను సగానికి పదేపదే విభజించడంపై ఆధారపడి ఉంటుంది. ఫలితం ఆకట్టుకుంటుంది! మేము సంఖ్యను వెతకడానికి సరళ శోధనను ఉపయోగిస్తే, మనకు గరిష్టంగా 10 పోలికలు అవసరమవుతాయి, కానీ బైనరీ శోధనతో, మేము కేవలం 3తో పనిని పూర్తి చేసాము! చెత్త సందర్భంలో, 4 పోలికలు ఉంటాయి (చివరి దశలో మనం కోరుకున్న సంఖ్య మొదటిది కాకుండా మిగిలిన అవకాశాలలో రెండవది. కాబట్టి దాని సంక్లిష్టత గురించి ఏమిటి? ఇది చాలా ఆసక్తికరమైన అంశం :) బైనరీ శోధన అల్గోరిథం లీనియర్ సెర్చ్ అల్గారిథమ్ (అంటే సాధారణ పునరావృతం) కంటే శ్రేణిలోని మూలకాల సంఖ్యపై చాలా తక్కువగా ఆధారపడి ఉంటుంది. శ్రేణిలో 10 మూలకాలతో , సరళ శోధనకు గరిష్టంగా 10 పోలికలు అవసరం, కానీ బైనరీ శోధనకు గరిష్టంగా 4 పోలికలు అవసరం. అది 2.5 కారకం ద్వారా తేడా. కానీ 1000 మూలకాల శ్రేణి కోసం , ఒక సరళ శోధనకు గరిష్టంగా 1000 పోలికలు అవసరం, కానీ బైనరీ శోధనకు 10 మాత్రమే అవసరం ! ఇప్పుడు తేడా 100 రెట్లు! గమనిక:శ్రేణిలోని మూలకాల సంఖ్య 100 రెట్లు పెరిగింది (10 నుండి 1000 వరకు), కానీ బైనరీ శోధనకు అవసరమైన పోలికల సంఖ్య కేవలం 2.5 (4 నుండి 10 వరకు) కారకం ద్వారా పెరిగింది. మేము 10,000 మూలకాలను పొందినట్లయితే , వ్యత్యాసం మరింత ఆకర్షణీయంగా ఉంటుంది: సరళ శోధన కోసం 10,000 పోలికలు మరియు బైనరీ శోధన కోసం మొత్తం 14 పోలికలు . మరలా, మూలకాల సంఖ్య 1000 రెట్లు పెరిగితే (10 నుండి 10000 వరకు), అప్పుడు పోలికల సంఖ్య కేవలం 3.5 కారకం (4 నుండి 14 వరకు) పెరుగుతుంది. బైనరీ శోధన అల్గోరిథం యొక్క సంక్లిష్టత సంవర్గమానం , లేదా, మనం పెద్ద O సంజ్ఞామానాన్ని ఉపయోగిస్తే, O(log n). అలా ఎందుకు అంటారు? సంవర్గమానం ఘాతాంకానికి వ్యతిరేకం వంటిది. బైనరీ సంవర్గమానం అనేది సంఖ్యను పొందేందుకు సంఖ్య 2ని పెంచాల్సిన శక్తి. ఉదాహరణకు, బైనరీ సెర్చ్ అల్గారిథమ్‌ని ఉపయోగించి మనం శోధించాల్సిన 10,000 ఎలిమెంట్స్ ఉన్నాయి. ప్రస్తుతం, మీరు దీన్ని చేయడానికి గరిష్టంగా 14 పోలికలు అవసరమవుతాయని తెలుసుకోవడానికి విలువల పట్టికను చూడవచ్చు. కానీ ఎవరూ అలాంటి పట్టికను అందించకపోతే మరియు మీరు ఖచ్చితమైన గరిష్ట సంఖ్యలో పోలికలను లెక్కించాల్సిన అవసరం ఉంటే? మీరు ఒక సాధారణ ప్రశ్నకు సమాధానం ఇవ్వాలి: మీరు సంఖ్య 2ని ఏ శక్తికి పెంచాలి, తద్వారా ఫలితం తనిఖీ చేయవలసిన మూలకాల సంఖ్య కంటే ఎక్కువగా ఉంటుంది లేదా సమానంగా ఉంటుంది? 10,000 కోసం, ఇది 14వ శక్తి. 2 నుండి 13వ శక్తి చాలా చిన్నది (8192), కానీ 2 నుండి 14వ శక్తి = 16384, మరియు ఈ సంఖ్య మన పరిస్థితిని సంతృప్తిపరుస్తుంది (ఇది శ్రేణిలోని మూలకాల సంఖ్య కంటే ఎక్కువ లేదా సమానంగా ఉంటుంది). మేము లాగరిథమ్‌ని కనుగొన్నాము: 14. మనకు ఎన్ని పోలికలు అవసరం కావచ్చు! :) అల్గారిథమ్‌లు మరియు అల్గారిథమిక్ సంక్లిష్టత అనేది ఒక పాఠానికి సరిపోయేంత విస్తృతమైన అంశం. కానీ తెలుసుకోవడం చాలా ముఖ్యం: చాలా ఉద్యోగ ఇంటర్వ్యూలలో అల్గారిథమ్‌లతో కూడిన ప్రశ్నలు ఉంటాయి. సిద్ధాంతం కోసం, నేను మీ కోసం కొన్ని పుస్తకాలను సిఫార్సు చేయగలను. మీరు " గ్రోకింగ్ అల్గారిథమ్స్ " తో ప్రారంభించవచ్చు . ఈ పుస్తకంలోని ఉదాహరణలు పైథాన్‌లో వ్రాయబడ్డాయి, కానీ పుస్తకం చాలా సరళమైన భాష మరియు ఉదాహరణలను ఉపయోగిస్తుంది. ఇది ఒక అనుభవశూన్యుడు కోసం ఉత్తమ ఎంపిక మరియు, ఇంకా ఏమి, ఇది చాలా పెద్దది కాదు. మరింత తీవ్రమైన పఠనంలో, రాబర్ట్ లాఫోర్ మరియు రాబర్ట్ సెడ్జ్‌విక్‌ల పుస్తకాలు మా వద్ద ఉన్నాయి. రెండూ జావాలో వ్రాయబడ్డాయి, ఇది మీకు నేర్చుకోవడం కొంచెం సులభతరం చేస్తుంది. అన్నింటికంటే, మీకు ఈ భాష బాగా తెలుసు! :) మంచి గణిత నైపుణ్యాలు ఉన్న విద్యార్థులకు, థామస్ కోర్మెన్ పుస్తకం ఉత్తమ ఎంపిక . కానీ సిద్ధాంతం మాత్రమే మీ కడుపు నింపదు! జ్ఞానం != సామర్థ్యం . మీరు హ్యాకర్‌ర్యాంక్ మరియు లీట్‌కోడ్‌లో అల్గారిథమ్‌లతో కూడిన సమస్యలను పరిష్కరించడాన్ని ప్రాక్టీస్ చేయవచ్చు . ఈ వెబ్‌సైట్‌ల నుండి టాస్క్‌లు తరచుగా Google మరియు Facebookలో ఇంటర్వ్యూల సమయంలో కూడా ఉపయోగించబడతాయి, కాబట్టి మీరు ఖచ్చితంగా విసుగు చెందలేరు :) ఈ పాఠ్యాంశాన్ని బలోపేతం చేయడానికి, మీరు YouTubeలో పెద్ద O సంజ్ఞామానం గురించి ఈ అద్భుతమైన వీడియోను చూడాలని నేను సిఫార్సు చేస్తున్నాను. తదుపరి పాఠాలలో కలుద్దాం! :)