Нишонаи O(n) аз куҷо пайдо мешавад ва чаро аз O(n²) беҳтар аст?

O(n) نوٹیشن (یا Big O نوٹیشن) ایک فنکشن کے اَسمپٹوٹک رویے کو بیان کرتا ہے، جو کہ وقت یا میموری کی خصوصیت رکھتا ہے، جو کہ الگورتھم کے ذریعہ استعمال ہوتی ہے، جیسے ہی ان پٹ ڈیٹا کا سائز (n) بڑھتا ہے۔

ریاضیاتی طور پر، f(n) = O(g(n)) کا مطلب ہے کہ مثبت مستقل c اور n₀ موجود ہیں، ایسے کہ تمام n ≥ n₀ کے لیے، f(n) ≤ c * g(n)۔ g(n) یہاں f(n) کے غالب جز کو ظاہر کرتا ہے، مستقل اور کم درجے کے اجزاء کو نظر انداز کرتے ہوئے۔

مثال کے طور پر، ایک الگورتھم جو 3n + 5 آپریشنز انجام دیتا ہے، اس کی پیچیدگی O(n) ہوگی، کیونکہ بڑے n کے لیے، 3n جز غالب ہوتا ہے، اور 5 مستقل طور پر کم اہم ہوتا ہے۔ ہم 3 اور 5 کو نظر انداز کرتے ہیں، اور صرف n کو رہنے دیتے ہیں۔

O(n) کی پیچیدگی کا مطلب ہے کہ عمل کا وقت (یا استعمال شدہ میموری) لائنر طور پر بڑھتا ہے، جب ان پٹ ڈیٹا کا سائز بڑھتا ہے۔ اگر ان پٹ ڈیٹا دگنا ہو جائے، تو عمل کا وقت تقریباً دگنا ہو جائے گا۔

O(n²) کی پیچیدگی کا مطلب ہے کہ عمل کا وقت مربع کے سائز کے ساتھ بڑھتا ہے۔ اگر ان پٹ ڈیٹا دگنا ہو جائے، تو عمل کا وقت تقریباً چار گنا بڑھ جائے گا۔

O(n) بہتر ہے O(n²) سے، کیونکہ جب n بڑھتا ہے، تو n کا فنکشن بہت سست روی سے بڑھتا ہے، اس سے یہ ظاہر ہوتا ہے کہ لکیری پیچیدگی والے الگورتھمز بڑے ڈیٹا سیٹس کے لیے زیادہ قابلِ پیمائش ہوتے ہیں، اور مربع پیچیدگی والے الگورتھمز کے مقابلے میں بہتر اسکیل کرتے ہیں۔

مثال کے طور پر:

n	O(n) = n	O(n²) = n²
1	1	1
10	10	100
100	100	10000
1000	1000	1000000

جیسا کہ جدول سے ظاہر ہے، n کے بڑھنے کے ساتھ، O(n) اور O(n²) کے درمیان کارکردگی کا فرق نمایاں ہوتا ہے، اور یہ فرق تیزی سے بڑھتا ہے۔

O(n) کا ایک مثال الگورتھم:

# ایک سادہ لوپ جو فہرست کے تمام عناصر پر ایک بار چلتا ہے
def linear_search(arr, target):
  for item in arr:
    if item == target:
      return True
  return False

O(n²) کا ایک مثال الگورتھم:

# تمام جوڑوں کے عناصر کا موازنہ کرنے کے لیے nested loops

def bubble_sort(arr):
  n = len(arr)
  for i in range(n):
    for j in range(0, n - i - 1):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]

جب الگورتھم کا انتخاب کیا جاتا ہے، تو کم اسیمپٹوٹک پیچیدگی والے الگورتھمز کو ترجیح دی جاتی ہے، کیونکہ یہ براہ راست کارکردگی اور پیمائش کو متاثر کرتا ہے۔