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

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

• ڪپڙو
• صاف
• چڱي طرح کاڌو

ڪهڙو الگورتھم توهان کي هن نتيجو حاصل ڪرڻ جي اجازت ڏيندو؟

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

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

1. خريد ڪريو يا انٽرنيٽ تي ڊائون لوڊ ڪريو "روسي ذاتي نالن جي ڊڪشنري" 1966 ايڊيشن.
2. هن لغت ۾ اسان جي لسٽ تي هر نالو ڳوليو.
3. ڪاغذ جي هڪ ٽڪري تي لکو ته لغت جي ڪهڙي صفحي تي نالو آهي.
4. ڪاغذ جي هڪ ٽڪري تي نوٽس استعمال ڪندي نالن کي ترتيب ڏيو.

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

int[] numbers = new int[100];
// ..заполняем массив числами

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