کوڈ کے دو ٹکڑے ایک چھوٹے ٹیسٹ کیس پر ایک جیسے نتائج پیدا کر سکتے ہیں اور حقیقی ڈیٹا آنے پر بالکل مختلف برتاؤ کر سکتے ہیں۔ بگ او نوٹیشن وہ طریقہ ہے جس سے کمپیوٹر سائنسدان اس فرق کو درست طریقے سے بیان کرتے ہیں۔
A-Level توسیع
"O" واقعی کیا مطلب رکھتا ہے
بگ او ایک الگورتھم کی نمو کی شرح بیان کرتا ہے — ان پٹ کا سائز بڑھنے کے ساتھ آپریشنز کی تعداد کیسے بڑھتی ہے، جسے روایتی طور پر n کہا جاتا ہے۔
نمو کی شرحیں جو واقعی اہم ہیں
مٹھی بھر نمو کی شرحیں تقریباً ہر الگورتھم کا احاطہ کرتی ہیں جس کا آپ سامنا کریں گے، ڈیٹا بڑھنے کے ساتھ بہترین سے بدترین تک:
- O(1) — مستقل۔ ان پٹ کے سائز سے قطع نظر یکساں تعداد میں قدم، جیسے یہ چیک کرنا کہ کوئی فہرست خالی ہے یا نہیں۔
- O(log n) — لوگارتھمک۔ n بڑھنے کے ساتھ آپریشنز بہت آہستہ بڑھتے ہیں — مثال کے طور پر، ایک ترتیب شدہ فہرست پر بائنری سرچ۔
- O(n) — لکیری۔ ان پٹ کو دگنا کریں، کام دگنا ہو جاتا ہے۔
- O(n²) — دوہرا۔ ان پٹ کو دگنا کریں، کام چار گنا ہو جاتا ہے۔
چھوٹے n پر یہ منحنی خطوط ایک جیسے نظر آتے ہیں — جو فرق طے کرتا ہے کہ کون سا الگورتھم واقعی حقیقی دنیا کے ڈیٹا سے بچتا ہے وہ صرف n بڑا ہونے پر ہی واضح ہوتا ہے۔
Try it yourself — drag the slider to change the input size (n), and watch how many operations each growth rate actually needs.
Input size: n = 10
At n = 10, an O(n²) approach needs 100 operations — 10× more than the O(n) approach doing the exact same job.
ایک دوہرا الگورتھم، O(n²)، جو 10 آئٹمز کے لیے 100 آپریشنز کرتا ہے وہ 1,000 آئٹمز کے لیے 1,000,000 آپریشنز کرتا ہے — 100 گنا ڈیٹا کے لیے 100 گنا کام نہیں، بلکہ 10,000 گنا۔
امتحان طرز کا سوال
ایک الگورتھم 4 آئٹمز کے لیے 8 آپریشنز، 8 آئٹمز کے لیے 32 آپریشنز، اور 16 آئٹمز کے لیے 128 آپریشنز لیتا ہے۔ اپنی دلیل ظاہر کرتے ہوئے اس کی بگ او نمو کی شرح متعین کریں۔ [3 نمبر]
نمونہ جواب اور نمبروں کی تقسیم دکھائیں
- ان لگاتار حالات کا موازنہ کریں جہاں n دوگنا ہوتا ہے: 4 → 8، اور 8 → 16 (1 نمبر)
- ہر بار آپریشنز کی تعداد چار گنا ہو جاتی ہے: 8 → 32 (×4)، اور 32 → 128 (×4) (1 نمبر)
- جب n کو دوگنا کرنے سے آپریشنز کی تعداد چار گنا ہو جاتی ہے (×4 = ×2²)، تو یہ مربعی نمو (quadratic growth) کی علامت ہے: O(n²) (1 نمبر)
ممتحن کس بات پر توجہ دیتا ہے: n کے دوگنا ہونے اور آپریشنز پر نتیجتاً ملنے والے ضرب کار کے درمیان مخصوص پیٹرن کی شناخت کریں — یہی تناسب (یہاں، ہر دوگنا ہونے پر ×4) حقیقتاً نمو کی شرح کی شناخت کرتا ہے، نہ کہ محض خام اعداد۔
عام غلطی: یہ فرض کرنا کہ یہ خطی نمو ہے محض اس لیے کہ اعداد 'مسلسل بڑے ہو رہے ہیں'، بغیر اس دوگنا ہونے والے تعلق کی جانچ کیے جو O(n) (n کے دوگنا ہونے پر ×2) کو O(n²) (دوگنا ہونے پر ×4) سے الگ کرتا ہے۔
عملی طور پر نمو کی شرحوں کے درمیان فرق کیوں اہم ہے
چھوٹے ٹیسٹ ڈیٹا کے ساتھ، ایک O(n²) الگورتھم اور ایک O(n log n) الگورتھم دونوں ایک سیکنڈ کے حصے میں ختم ہو سکتے ہیں۔ اسی ان پٹ کو اس سائز تک بڑھائیں جسے ایک حقیقی پروڈکٹ واقعی سنبھالتا ہے، اور O(n²) طریقہ حقیقی گھنٹے لے سکتا ہے جہاں O(n log n) طریقہ سیکنڈ لیتا ہے۔
صحیح کوڈ لکھنے سے آگے یہ کیوں اہم ہے
کوئی بھی پروگرامر ایسا کوڈ لکھ سکتا ہے جو صحیح جواب پیدا کرتا ہے۔ اگر کمپیوٹر سائنس کچھ ایسا ہے جسے آپ یا آپ کے بچے کو یہ سمجھایا جانا چاہیے کہ ایک طریقہ دوسرے سے بہتر کیوں ہے، صرف سنٹیکس نہیں، تو یہی بالکل وہ ہے جو ہماری GCSE اور A-Level کمپیوٹر سائنس کی ٹیوشن فراہم کرتی ہے، اور آپ مکمل سیکھنے کا راستہ یہاں دیکھ سکتے ہیں۔
عمومی سوالات
ہم مستقل اور چھوٹی اصطلاحات کو کیوں نظر انداز کرتے ہیں؟
بگ او جان بوجھ کر ایک مخصوص سوال کا جواب دینے کے لیے بنایا گیا ہے — ان پٹ بہت بڑا ہونے پر رن ٹائم کیسے بڑھتا ہے — اور n جتنا بڑا ہوتا ہے مستقل اتنے ہی کم اہم ہوتے ہیں۔
کیا کم بگ او ہمیشہ عملی طور پر بہتر انتخاب ہے؟
خودکار طور پر نہیں — چھوٹے ان پٹ کے لیے، ایک بدتر بگ او لیکن بہت چھوٹے مستقل عنصر والا الگورتھم واقعی عملی طور پر تیز چل سکتا ہے۔
بگ او کو واقعی پروگرامرز روزمرہ میں کیسے استعمال کرتے ہیں، صرف انٹرویو میں نہیں؟
یہ وہ طریقہ ہے جس سے ایک ڈیولپر پیشین گوئی کرتا ہے کہ کیا کوئی طریقہ حقیقی (بہت بڑا) ڈیٹا آنے پر بھی کام کرے گا۔ ایک غیر ترتیب شدہ فہرست میں تلاش کرنا O(n) ہے؛ ایک ترتیب شدہ فہرست میں بائنری سرچ O(log n) ہے۔
قارئین کی درجہ بندی اور تبصرے
اس مضمون کو کئی مختلف پہلوؤں پر درجہ دیں — آپ کی درجہ بندی دوسرے قارئین کی مدد کرتی ہے، اور ہمیں بہتر بنانے میں مدد کرتی ہے۔
کیا یہ مضمون مفید تھا؟
ہمیں اپنی رائے بتائیں — کوئی اصلاح، کوئی سوال جس کا جواب نہیں ملا، یا کوئی موضوع جسے آپ اگلی بار کور ہوتے دیکھنا چاہتے ہیں۔
بات کرنا پسند کریں گے؟ اپنی سہولت کے وقت مفت ویڈیو کال بک کریں: فوری سوال کے لیے 15 منٹ، باقی کے لیے 30 منٹ۔ اوقات آپ کے اپنے ٹائم زون میں دکھائے جاتے ہیں۔
مصنف کے بارے میں
Sudershan Soni
موسٹک سروسز میں بانی اور مرکزی استاد — MSc اہلیت یافتہ ریاضی، سائنس، کمپیوٹر سائنس اور STEM کے استاد، 20 سال سے زائد پیشہ ورانہ تجربے کے ساتھ، 11+ اور GCSE سے A-Level اور اس سے آگے تک کے طلبہ کو دنیا بھر میں آن لائن پڑھاتے ہیں۔
مکمل پروفائل پڑھیں