الگورتھم جي پيچيدگي

سلام اڄ جو سبق باقي سبق کان ٿورو مختلف هوندو. ان ۾ فرق هوندو ته اهو صرف اڻ سڌي طرح جاوا سان لاڳاپيل آهي. اهو چيو ته، هي موضوع هر پروگرامر لاء تمام ضروري آهي. اسان algorithms بابت ڳالهائڻ وارا آهيون . هڪ الگورتھم ڇا آهي؟ سادي اصطلاحن ۾، اهو عملن جو ڪجهه سلسلو آهي جيڪو گهربل نتيجو حاصل ڪرڻ لاء مڪمل ٿيڻ گهرجي . اسان اڪثر روزمره جي زندگي ۾ الگورتھم استعمال ڪندا آهيون. مثال طور، هر صبح توهان وٽ هڪ خاص ڪم آهي: اسڪول يا ڪم تي وڃو، ۽ ساڳئي وقت:

• ڪپڙو
• صاف
• فيڊ

ڪهڙو الورورٿم توهان کي اهو نتيجو حاصل ڪرڻ جي اجازت ڏئي ٿو؟

1. الارم ڪلاڪ استعمال ڪندي جاڳڻ.
2. شاور وٺو ۽ پاڻ کي ڌوء.
3. ناشتو ۽ ڪافي يا چانهه ٺاهيو.
4. کائو.
5. جيڪڏهن توهان اڳئين شام پنهنجا ڪپڙا استري نه ڪيا هئا، ته پوءِ ان کي استري ڪريو.
6. ڪپڙا پايو.
7. گهر ڇڏي وڃ.

عملن جو هي سلسلو ضرور توهان کي گهربل نتيجو حاصل ڪرڻ ڏيندو. پروگرامنگ ۾، اسان مسلسل ڪم مڪمل ڪرڻ لاء ڪم ڪري رهيا آهيون. انهن ڪمن جو هڪ اهم حصو الگورتھم استعمال ڪري سگهجي ٿو جيڪي اڳ ۾ ئي سڃاتل آهن. مثال طور، فرض ڪريو ته توھان جو ڪم ھي آھي: ھڪ صف ۾ 100 نالن جي لسٽ ترتيب ڏيو . اهو ڪم بلڪل سادو آهي، پر اهو مختلف طريقن سان حل ڪري سگهجي ٿو. هتي هڪ ممڪن حل آهي: نالا ترتيب ڏيڻ لاءِ الگورتھم

1. خريد ڪريو يا ڊائونلوڊ ڪريو 1961 جو ايڊيشن Webster's Third New International Dictionary.
2. هن ڊڪشنري ۾ اسان جي لسٽ مان هر نالو ڳوليو.
3. ڪاغذ جي هڪ ٽڪري تي، لغت جو صفحو لکو جنهن تي نالو موجود آهي.
4. نالن کي ترتيب ڏيڻ لاءِ ڪاغذ جا ٽڪرا استعمال ڪريو.

ڇا عملن جو اهڙو سلسلو اسان جو ڪم پورو ڪندو؟ ها، اهو ضرور ٿيندو. ڇا هي حل موثر آهي ؟ مشڪل سان. هتي اسان الورگرافس جي هڪ ٻئي اهم پهلوئن ڏانهن اچون ٿا: انهن جي ڪارڪردگي . ھن ڪم کي پورو ڪرڻ جا ڪيترائي طريقا آھن. پر ٻئي پروگرامنگ ۽ عام زندگي ۾، اسان کي سڀ کان وڌيڪ موثر طريقو چونڊڻ چاهيون ٿا. جيڪڏهن توهان جو ڪم ٽوسٽ جو مکڻ جو ٽڪرو ٺاهڻ آهي، ته توهان ڪڻڪ پوکڻ ۽ ڳئون کير ڏيڻ شروع ڪري سگهو ٿا. پر اهو هڪ غير موثر حل هوندو - اهو گهڻو وقت وٺندو ۽ تمام گهڻو پئسو خرچ ڪندو. توهان صرف ماني ۽ مکڻ خريد ڪندي پنهنجو سادو ڪم پورو ڪري سگهو ٿا. جيتوڻيڪ اهو توهان کي مسئلو حل ڪرڻ جي اجازت ڏئي ٿو، ڪڻڪ ۽ ڳئون شامل ڪرڻ واري الگورتھم عملي طور تي استعمال ڪرڻ لاء تمام پيچيده آهي. پروگرامنگ ۾، اسان وٽ خاص نوٽيشن آهي جنهن کي بگ O نوٽشن سڏيو ويندو آهي ته جيئن الگورتھم جي پيچيدگي جو اندازو لڳايو وڃي. بگ O اهو اندازو لڳائڻ ممڪن بڻائي ٿو ته هڪ الورورٿم جي عمل جو وقت ان پٽ ڊيٽا جي سائيز تي ڪيترو منحصر آهي . اچو ته آسان ترين مثال ڏسو: ڊيٽا جي منتقلي. تصور ڪريو ته توھان کي فائل جي صورت ۾ ھڪڙي ڊگھي فاصلي تي ڪجھ معلومات موڪلڻ جي ضرورت آھي (مثال طور، 5000 ميل). ڪهڙو الورورٿم سڀ کان وڌيڪ ڪارائتو هوندو؟ اهو منحصر آهي ڊيٽا تي جيڪو توهان ڪم ڪري رهيا آهيو. مثال طور، فرض ڪريو اسان وٽ هڪ آڊيو فائل آهي جيڪا 10 MB آهي. انهي حالت ۾، سڀ کان وڌيڪ موثر الگورتھم انٽرنيٽ تي فائل موڪلڻ آهي. اهو ڪجهه منٽن کان وڌيڪ نه وٺي سگهيو! اچو ته اسان جي الگورتھم کي بحال ڪريو: "جيڪڏهن توهان 5000 ميلن جي فاصلي تي فائلن جي صورت ۾ معلومات منتقل ڪرڻ چاهيو ٿا، توهان کي انٽرنيٽ ذريعي ڊيٽا موڪلڻ گهرجي". تمام سٺو. هاڻي اچو ته ان جو تجزيو. ڇا اهو اسان جي ڪم کي پورو ڪري ٿو؟ خير، ها، اهو ڪري ٿو. پر اسان ان جي پيچيدگي بابت ڇا چئي سگهون ٿا؟ ها، هاڻي شيون وڌيڪ دلچسپ ٿي رهيون آهن. حقيقت اها آهي ته اسان جي الگورتھم ان پٽ ڊيٽا تي تمام گهڻو منحصر آهي، يعني، فائلن جي سائيز. جيڪڏهن اسان وٽ 10 ميگا بائيٽ آهن، پوء سڀ ڪجهه ٺيڪ آهي. پر ڇا جيڪڏهن اسان کي 500 ميگا بائيٽ موڪلڻ جي ضرورت آهي؟ 20 گيگا بائيٽ؟ 500 terabytes؟ 30 petabytes؟ ڇا اسان جو الگورتھم ڪم ڪرڻ بند ڪري ڇڏيندو؟ نه، ڊيٽا جي انهن سڀني مقدارن کي حقيقت ۾ منتقل ڪري سگهجي ٿو. ڇا اهو وڌيڪ وقت وٺندو؟ ها، اهو ٿيندو! ھاڻي اسان ڄاڻون ٿا اسان جي الگورتھم جي ھڪ اھم خصوصيت: ڊيٽا جو جيترو وڏو مقدار موڪلڻ لاءِ، اوترو ئي اھو الورورٿم کي ھلائڻ ۾ وڌيڪ وقت وٺندو . پر اسان چاهيون ٿا ته هن رشتي جي وڌيڪ صحيح سمجهه (انپٽ ڊيٽا جي سائيز ۽ ان کي موڪلڻ لاء گهربل وقت جي وچ ۾). اسان جي حالت ۾، الورورٿمڪ پيچيدگي لڪير آهي. ”لينئر“ جو مطلب آهي ته جيئن جيئن ان پٽ ڊيٽا جو مقدار وڌندو، تيئن ان کي موڪلڻ ۾ لڳندو وقت لڳ ڀڳ وڌندو. جيڪڏهن ڊيٽا جو مقدار ٻيڻو ٿي وڃي ته پوءِ ان کي موڪلڻ لاءِ گهربل وقت ٻيڻو ٿي ويندو. جيڪڏهن ڊيٽا 10 ڀيرا وڌائي ٿي، پوء ٽرانسميشن جو وقت 10 ڀيرا وڌي ويندو. وڏي O نوٽشن کي استعمال ڪندي، اسان جي الگورتھم جي پيچيدگي کي O(n) طور ظاهر ڪيو ويو آهي . توهان کي ياد رکڻ گهرجي ته هي اشارو مستقبل لاءِ - اهو هميشه لڪير جي پيچيدگي سان الگورتھم لاءِ استعمال ٿيندو آهي. ياد رهي ته اسان ڪيترن ئي شين بابت نه ڳالهائي رهيا آهيون جيڪي هتي مختلف ٿي سگهن ٿيون: انٽرنيٽ جي رفتار، اسان جي ڪمپيوٽر جي ڪمپيوٽر جي طاقت، وغيره. جڏهن هڪ الگورٿم جي پيچيدگي جو اندازو لڳايو، اهو آسان ناهي ته انهن عنصرن تي غور ڪرڻ - ڪنهن به صورت ۾، اهي اسان جي ڪنٽرول کان ٻاهر آهن. بگ او نوٽيشن پاڻ الگورٿم جي پيچيدگي کي ظاهر ڪري ٿو، نه ته "ماحول" جنهن ۾ اهو هلندو آهي. اچو ته اسان جي مثال سان جاري رکون. فرض ڪريو ته اسان آخرڪار سکيو ته اسان کي 800 ٽيرا بائيٽس جون فائلون موڪلڻ گهرجن. اسان ڪري سگهون ٿا، يقينا، اسان جي ڪم کي انٽرنيٽ تي موڪلڻ ذريعي. هتي صرف هڪ مسئلو آهي: معياري گهريلو ڊيٽا ٽرانسميشن جي شرحن تي (100 ميگاابٽ في سيڪنڊ)، اهو لڳ ڀڳ 708 ڏينهن وٺندو. لڳ ڀڳ 2 سال! :O اسان جو الگورٿم واضح طور تي هتي مناسب ناهي. اسان کي ڪنهن ٻئي حل جي ضرورت آهي! اوچتو، آئي ٽي ديو Amazon اسان جي بچاء لاء اچي ٿو! Amazon جي سنو موبائيل سروس اسان کي موبائيل اسٽوريج تي ڊيٽا جي وڏي مقدار کي اپلوڊ ڪرڻ جي اجازت ڏئي ٿي ۽ پوءِ ان کي ٽرڪ ذريعي گهربل ايڊريس تي پهچايو! تنهن ڪري، اسان وٽ هڪ نئون الگورتھم آهي! "جيڪڏهن توهان 5000 ميلن جي فاصلي تي فائلن جي صورت ۾ معلومات منتقل ڪرڻ چاهيو ٿا ۽ ائين ڪرڻ سان انٽرنيٽ ذريعي موڪلڻ ۾ 14 ڏينهن کان وڌيڪ وقت لڳندو، توهان کي ايمازون ٽرڪ تي ڊيٽا موڪلڻ گهرجي." اسان هتي 14 ڏينهن پاڻمرادو چونڊيو. اچو ته اهو سڀ کان ڊگهو عرصو آهي جيڪو اسان انتظار ڪري سگهون ٿا. اچو ته اسان جي الگورتھم جو تجزيو ڪيو. ان جي رفتار بابت ڇا؟ جيتوڻيڪ ٽرڪ صرف 50 ميل في ڪلاڪ جي رفتار سان سفر ڪري ٿو، اهو صرف 100 ڪلاڪن ۾ 5000 ميلن کي پورو ڪري ڇڏيندو. هي چار ڏينهن کان ٿورو مٿي آهي! اهو انٽرنيٽ تي ڊيٽا موڪلڻ جي اختيار کان گهڻو بهتر آهي. ۽ هن الگورتھم جي پيچيدگي بابت ڇا؟ ڇا اهو پڻ لڪير آهي، يعني O(n)؟ نه اهو ناهي. آخرڪار، ٽرڪ کي پرواه ناهي ته توهان ان کي ڪيترو وزن کڻندا آهيو - اهو اڃا تائين ساڳئي رفتار تي هلندو ۽ وقت تي پهچندو. ڇا اسان وٽ 800 ٽيرا بائيٽ آهن، يا ان کان 10 ڀيرا، ٽرڪ اڃا تائين 5 ڏينهن اندر پنهنجي منزل تي پهچندي. ٻين لفظن ۾، ٽرڪ تي ٻڌل ڊيٽا جي منتقلي الورورٿم مسلسل پيچيدگي آهي . هتي، "مسلسل" جو مطلب آهي ته اهو ان پٽ ڊيٽا جي سائيز تي منحصر ناهي. ٽرڪ ۾ 1GB فليش ڊرائيو رکو، اهو 5 ڏينهن اندر پهچي ويندو. 800 ٽيرا بائيٽ ڊيٽا تي مشتمل ڊسڪ ۾ وجھو، اھو 5 ڏينھن اندر اچي ويندو. جڏهن وڏي O نوٽيفڪيشن استعمال ڪندي، مسلسل پيچيدگي کي O(1) ذريعي ظاهر ڪيو ويندو آهي .۽ 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، عناصر ڪٿي به نه ٿا وڃن. لنڪس (يا حوالا) اپڊيٽ ٿيل آهن (جيڪڏهن توهان وساريو ته LinkedList ڪيئن ڪم ڪري ٿي، اسان جي پراڻي سبقن مان هڪ کي ڏسو ). جيڪڏهن اسان جي لسٽ ۾ پهريون نمبر آهي x، ۽ اسان لسٽ جي سامهون نمبر y داخل ڪندا آهيون، پوء اسان کي اهو ڪرڻ جي ضرورت آهي:

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

جڏهن اسان لنڪس کي اپڊيٽ ڪندا آهيون، اسان کي پرواه ناهي ته ڪيترا نمبر اڳ ۾ ئي آهنLinkedList ، ڇا هڪ يا هڪ ارب. الورورٿم جي پيچيدگي مسلسل آهي، يعني O(1).

Logarithmic پيچيدگي

پريشان نہ ٿيو! :) جيڪڏهن لفظ "لوگارٿمڪ" توهان کي هن سبق کي بند ڪرڻ ۽ پڙهڻ بند ڪرڻ چاهي ٿو، صرف ڪجهه منٽن لاءِ رکو. هتي ڪو به چريو رياضي نه ٿيندو (ٻين هنڌن وانگر ڪافي وضاحتون آهن)، ۽ اسان هر مثال کي ڌار ڪنداسين. تصور ڪريو ته توهان جو ڪم 100 نمبرن جي هڪ صف ۾ هڪ مخصوص نمبر ڳولڻ آهي. وڌيڪ واضح طور تي، توهان کي چيڪ ڪرڻ جي ضرورت آهي ته ڇا اهو آهي يا نه. جيئن ئي گهربل نمبر ملي ٿو، ڳولا ختم ٿي ويندي آهي، ۽ توهان ڪنسول ۾ هيٺيون ڏيکاريندا آهيو: "گهربل نمبر مليو هو! ان جي انڊيڪس صف ۾ = ....." توهان اهو ڪم ڪيئن پورو ڪندا؟ ھتي حل پڌرو آھي: توھان کي ھڪڙي ھڪڙي ترتيب جي عناصرن تي ھڪڙي ھڪڙي ترتيب ڏيڻ جي ضرورت آھي، پھريون (يا آخري کان) شروع ڪندي ۽ چيڪ ڪريو ته ڇا موجوده نمبر ھڪڙي سان ملندو آھي جنھن کي توھان ڳولي رھيا آھيو. ان جي مطابق، عملن جو تعداد سڌو سنئون ۾ عناصر جي تعداد تي منحصر آھي. جيڪڏهن اسان وٽ 100 نمبر آهن، ته پوء اسان کي ممڪن طور تي ايندڙ عنصر ڏانهن وڃڻ جي ضرورت پوندي 100 ڀيرا ۽ 100 مقابلي کي انجام ڏيو. جيڪڏهن 1000 انگ آهن، ته پوءِ 1000 مقابلو ٿي سگهي ٿو. اهو واضح طور تي لڪير پيچيدگي آهي، يعني O(n) . ۽ ھاڻي اسان پنھنجي مثال ۾ ھڪڙو سڌارو شامل ڪنداسين: صف جتي توھان کي ڳولھيو نمبر ڳولڻ جي ضرورت آھي وڌندي ترتيب سان ترتيب ڏنل آھي . ڇا اهو اسان جي ڪم جي حوالي سان ڪجهه تبديل ڪري ٿو؟ اسان اڃا تائين گهربل نمبر لاءِ برٽ فورس ڳولهي سگھون ٿا. پر متبادل طور تي، اسان استعمال ڪري سگهون ٿا معروف بائنري ڳولا الگورٿم . تصوير ۾ مٿين قطار ۾، اسان ڏسون ٿا هڪ ترتيب ڏنل صف. اسان کي ان ۾ نمبر 23 ڳولڻ جي ضرورت آهي. انگن تي ٻيهر ورجائڻ جي بدران، اسان صرف صف کي 2 حصن ۾ ورهايو ۽ صف ۾ وچين نمبر کي چيڪ ڪريو. اهو نمبر ڳولھيو جيڪو سيل 4 ۾ واقع آھي ۽ ان کي چيڪ ڪريو (تصوير ۾ ٻي قطار). هي نمبر 16 آهي، ۽ اسان 23 کي ڳولي رهيا آهيون. موجوده نمبر ان کان گهٽ آهي جيڪو اسان ڳولي رهيا آهيون. هن جو مطلب ڇا آهي؟ ان جو مطلب اهو آهي ته سڀ پوئين نمبر (جيڪي نمبر 16 کان اڳ موجود آهن) کي جانچڻ جي ضرورت ناهي : اهي ضمانت آهن انهن کان گهٽ هجڻ جي جنهن کي اسان ڳولي رهيا آهيون، ڇاڪاڻ ته اسان جي صف ترتيب ڏنل آهي! اسان باقي 5 عناصر جي وچ ۾ ڳولا جاري رکون ٿا. نوٽ:اسان صرف هڪ مقابلو ڪيو آهي، پر اسان اڳ ۾ ئي اڌ ممڪن اختيارن کي ختم ڪري ڇڏيو آهي. اسان وٽ صرف 5 عناصر رهجي ويا آهن. اسان پنهنجي پوئين قدم کي ورجائينداسين هڪ ڀيرو ٻيهر باقي سباري کي اڌ ۾ ورهائي ۽ ٻيهر وچين عنصر (تصوير ۾ ٽين قطار) وٺي. نمبر 56 آھي، ۽ اھو ان کان وڏو آھي جنھن کي اسين ڳولي رھيا آھيون. هن جو مطلب ڇا آهي؟ ان جو مطلب اهو آهي ته اسان ٻين 3 امڪانن کي ختم ڪري ڇڏيو آهي: نمبر 56 پاڻ سان گڏ گڏوگڏ ٻه نمبر ان کان پوء (ڇاڪاڻ ته اهي 23 کان وڌيڪ هجڻ جي ضمانت آهن، ڇاڪاڻ ته صف ترتيب ڏنل آهي). چيڪ ڪرڻ لاءِ اسان وٽ صرف 2 نمبر بچيا آهن (تصوير ۾ آخري قطار) - انگ اکر 5 ۽ 6 سان گڏ. اسان انهن مان پهرين چيڪ ڪريون ٿا، ۽ ڳوليون ٿا جيڪو اسان ڳولي رهيا هئاسين - نمبر 23! ان جي انڊيڪس 5 آهي! اچو ته اسان جي الگورتھم جي نتيجن کي ڏسو، ۽ پوء اسين ان جي پيچيدگي جو تجزيو ڪنداسين. رستي جي ذريعي، هاڻي توهان سمجهي رهيا آهيو ته هن کي بائنري ڳولا ڇو سڏيو ويندو آهي: اهو بار بار ڊيٽا کي اڌ ۾ ورهائڻ تي ڀاڙي ٿو. نتيجو شاندار آهي! جيڪڏهن اسان نمبر ڳولڻ لاءِ هڪ لڪير ڳولها استعمال ڪيون، اسان کي 10 مقابلي جي ضرورت پوندي، پر بائنري ڳولا سان، اسان اهو ڪم صرف 3 سان پورو ڪيو! بدترين صورت ۾، اتي 4 موازن هوندا (جيڪڏهن آخري مرحلي ۾ اسان چاهيون ٿا ته نمبر باقي امڪانن جو ٻيو نمبر هو، پهرين جي ڀيٽ ۾. پوء ان جي پيچيدگي بابت ڇا؟ هي هڪ تمام دلچسپ نقطو آهي :) بائنري ڳولا algorithm صف ۾ عنصرن جي تعداد تي لڪير سرچ الورورٿم جي ڀيٽ ۾ تمام گهٽ منحصر آهي (يعني، سادو ورجائي). صف ۾ 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 تائين) وڌائي ٿو. بائنري سرچ الورورٿم جي پيچيدگي logarithmic آهي ، يا، جيڪڏهن اسان وڏي O نوٽشن، O(log n) استعمال ڪريون ٿا . اهو ڇو سڏيو ويندو آهي؟ لاگارٿم ظاھر جي ابتڙ آھي. بائنري لوگارٿم اها طاقت آهي جنهن کي حاصل ڪرڻ لاءِ نمبر 2 کي اٿڻو پوندو. مثال طور، اسان وٽ 10,000 عناصر آھن جيڪي اسان کي بائنري سرچ الگورتھم استعمال ڪندي ڳولڻ جي ضرورت آھي. في الحال، توھان ڏسي سگھوٿا قدرن جي جدول کي ڄاڻڻ لاءِ ته ائين ڪرڻ لاءِ وڌ ۾ وڌ 14 مقابلي جي ضرورت پوندي. پر ڇا جيڪڏهن ڪو به اهڙو ٽيبل مهيا نه ڪيو آهي ۽ توهان کي مقابلي جي صحيح وڌ ۾ وڌ تعداد کي ڳڻڻ جي ضرورت آهي؟ توهان کي صرف هڪ سادي سوال جو جواب ڏيڻ جي ضرورت آهي: توهان کي ڪهڙي طاقت جي ضرورت آهي نمبر 2 کي وڌائڻ لاءِ ته نتيجو ان کان وڌيڪ يا برابر آهي عنصرن جي تعداد جي جانچ ڪرڻ لاءِ؟ 10,000 لاء، اهو 14 طاقت آهي. 2 کان 13 پاور تمام ننڍو آهي (8192)، پر 2 کان 14 هين پاور = 16384 ، ۽ اهو انگ اسان جي حالت کي پورو ڪري ٿو (اها صف ۾ عناصر جي تعداد کان وڌيڪ يا برابر آهي). اسان کي لاگارٿم مليو: 14. اهو آهي ته اسان کي ڪيترين ئي مقابلي جي ضرورت هجي! :) Algorithms ۽ algorithmic پيچيدگي تمام وسيع آهي هڪ موضوع هڪ سبق ۾ فٽ ڪرڻ لاء. پر اهو ڄاڻڻ تمام ضروري آهي: نوڪري جا ڪيترائي انٽرويو سوالن ۾ شامل هوندا جن ۾ الگورتھم شامل آهن. نظريي لاءِ، مان توھان لاءِ ڪجھ ڪتاب سفارش ڪري سگھان ٿو. توھان شروع ڪري سگھو ٿا " گروڪنگ الگورتھم " سان. هن ڪتاب ۾ مثال پٿرن ۾ لکيل آهن، پر ڪتاب ۾ تمام سادي ٻولي ۽ مثال استعمال ڪيا ويا آهن. اهو هڪ شروعاتي لاء بهترين اختيار آهي ۽، وڌيڪ ڇا آهي، اهو تمام وڏو ناهي. وڌيڪ سنجيده پڙهڻ ۾، اسان وٽ رابرٽ لافور ۽ رابرٽ سيججڪ جا ڪتاب آهن . ٻئي جاوا ۾ لکيل آهن، جيڪي توهان لاءِ سکڻ کي ٿورو آسان بڻائي سگهندا. آخرڪار، توهان هن ٻولي سان ڪافي واقف آهيو! :) سٺي رياضي جي صلاحيتن سان شاگردن لاء، بهترين اختيار آهي Thomas Cormen جو ڪتاب . پر اڪيلو نظريو توهان جو پيٽ نه ڀريندو! علم = قابليت . توھان مشق ڪري سگھوٿا حل ڪرڻ جا مسئلا حل ڪرڻ ۾ جيڪي الگورتھم شامل آھن HackerRank ۽ LeetCode تي . انهن ويب سائيٽن جا ڪم اڪثر گوگل ۽ فيس بوڪ تي انٽرويوز دوران به استعمال ڪيا ويندا آهن، تنهنڪري توهان ضرور بور نه ٿيندا :) هن سبق جي مواد کي مضبوط ڪرڻ لاءِ، مان توهان کي صلاح ڏيان ٿو ته توهان يوٽيوب تي وڏي O نوٽشن بابت هي بهترين وڊيو ڏسو. ايندڙ سبقن ۾ ملنداسين! :)