Big O Notation in Mizo
Computera kan thil chawh dan (algorithm) hi a chipchiar dan (complexity) a zirin running time hrang hrang chhinchhiahna (symbol) hmanga pek a ni a, Big O notation tiin an sawi. O tih hrim hrim hi chu Order of tihna a ni. Order of operations and its time complexity tihna a ni ber. Complexity hrim hrim awm thei te chu:
- Big O = Upper Bound
- Omega = Lower Bound
- Theta = Exact/Tight Bound
- Little O = upper bound excluding the exact bound
tiin a hming an pe a ni. Computer-in thil a chawh dan chipchiar taka zirna a ni ber. Tun tumah hian Big O bik kan sawi dawn a ni. Big O hi a time complexity a zirin notation hrang hrang a awm ve thei a, chungte chu:
- O(1): Constant time
- O(log n): Logarithmic time
- O(n): Linear time
- O(n log n): Linearithmic time
- O(n2): Quadratic time
- O(2n): Exponential time
- O(n!): Factorial time
Big O a nih angin upper bound (worst case) sawina vek a ni.
Big O(1) Constant Time
Input len leh tetin algorithm hnathawh rei zawng tur a hril lo. Entirnan array a index hmanga lakchhuah te, Eng number pawh even or odd a nih leh nih loh check ang te hi. Algorithm-in a hna thawh zawh nan a hun mamawh chu eng input size-ah pawh a danglam ve lo tihna a ni. Python code en ila:
def is_even(num):
return num & 1 == 0
print(is_even(5))
Code en hian kan input size chu eng anga lian pawh ni se, rang takin even a nih leh nih loh kan hre thei nghal a. bitwise operator & hmangin kan number last bit chu 0 or 1 a nih leh nih loh a check ringawt a ni. Input size a len avangin a danglam ve lo.
O(log n) Logarithmic Time
O(log n) ah chuan kan input size a zirin Logarithm kalphung angin kan algorithm running time a pung thung a. Logarithm kalphungah chuan Number pakhat chawhchhuah nana base number amah leh a mah kan puntir ngai zat kan zawn a ngai a. Entirnan kan number base hi 2 lo ni ta se, 8 (input) chawhchhuah nana 2 kan puntir ngat zat chu 3 a ni. Tichuan 3 hi kan Logarithm chu a ni. Big O-ah chuan Log hian base 2 neisa anga ngaih a ni a chuvangin log(n) tiin an ziak a, a then chuan kim takin log2n tiin an ziak bawk. Tichuan kan entirna chu log 8=3 or log28=3 tiin kan dah thei tihna.
Linear function aiin a running time hi a pung chak lo zawk a, chuvangin thenkhat chuan slower version of linear function tiin an sawi thin bawk. logarithmic time complexity entirna tha deuh mai chu binary search hi a ni a. Binary search ah chuan item descending or ascending-a remdik sa atangin thil zawn tur a ni a. Kan thil zawn lai hian kan zawnna list chu a chanve zelin kan item zawn kan hmuh hma chu kan thenhrang a ni. Code hmangin tarlang leh zuai ila
def binary_search(arr, target):
start = 0
end = len(arr) - 1
while start <= end:
mid = (start + end) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target: #(List dinglam en a tul em)
start = mid + 1
else: #list veilam en a tul chuan list veilamah hian 12 awm ta se a lai tak thar chu 2 hi a ni dawn
end = mid - 1
return -1
print(binary_search([1, 2, 3, 4], 3)) #example data list 1-4-ah hian 3 position hi kan zawng a ni.
Code hian kan target (3) position hre turin binary search kalphung a hmang a. Tlawhchhuah (iteration) a neih apiangin list lai taka awm element kha a la chhuak a, kan target element nen a thuhmun leh thuhmun loh a check zel a ni. A lo in an chuan kan target element position a rawn print ang. A tet zawk chuan list lai tak atanga a dinglam zawng tlawhchhuah hna a thawk leh ang a, a lo lian zawk a nih chuan list lai tak veilam zela mi kha a endik leh ang. List tlawhchhuah kan neih apiangin list kha kan target a zirin list te zawk subarray/list ah kan siamchhawng leh zel a, a lai tak kha kan target nen a in ang em tih kan check zel a ni. Kan target kha listah awm lo ta se, worst case a ni dawn a, chuvangin log(n) time a in run a ngai dawn tihna a ni. Kan input(n) kha 4 lo ni ta se, log24 = 2, input hi 8-a a pun chuan log28 = 3 a tluk dawn a, 3-2=1 a ni. A leta input(n) a pun pawhin kan algorithm time punna hi 1 vel chauh a ni.
Big O(n) Linear Time
Big O notation hi computer-a thil chawh dan hmang leh dan (algorithm) kan chawhtur len dan (“n” tia dah thin a ni) a zira a hnathawh chak dan sawifiah nana hman a ni a. O(n) hi linear time complexity nei algorithm tia sawi a ni a, a awmzia ber chu kan chawh tur len zawng (size) ang zelin (linearly) a chawh rei zawng pawh a pung thei tihna a ni ber. Hei hi kan chawhtur a len viau pawhin a chawh rei zawng tur a pun hluai theih loh avangin algorithm hmantlak leh tha pangai tak anga ngaih a ni. Entirnan, thil zawn dan mawlmang tak (simple search algorithm) ah chuan kan zawnna tur array/list-a item awm zat kha item zawngchhuak tura kan endik ngai zat a ni an ti a; a chepa kaiin a mal te te-in kan enchhuah vek a ngai a, chuvangin time complexity O(n) a ni tiin an sawi a ni. Item awm zawng zawng va dapchhuak vek kher erawh a ngaih loh chang a awm thei a, mah se dapchhuah ngai vek a nih theih avangin item awm zat kha endik ngai zat anga sawi a lo ni ta a ni. Hetianga list-a mi a mal te te, a indawt dana thil zawn leh chhui hi linear search tiin an sawi bawk a ni. A hnuaiah hian Python language hmanga tih dan lo en ila:
def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
#Example of usage
arr = [1, 2, 3, 4, 5, 6]
x = 4
result = linear_search(arr, x)
if result != -1:
print("Element chu index position ", str(result),"-ah a awm")
else:
print("Element i zawn hi array-ah hian hmuh tur a awm lo")
A chunga code-ah hian kan function linear_search chuan chawhtur (input) atan arrparameter a nei a, kan zawn tur ber chu xangin a dah a ni. arr chhungah x kan zawng dawn tihna a ni. Tichuan for loop hmangin array chhunga item mal te te te chu kan endik a, kan x value nen a in ang em tih a indawt danin kan zawng a ni. A lo in an chuan kan x value awmna array index kan return a, a in an loh chuan -1 kan return dawn a ni . Codea kan hmuh ang hian 4 hi kan zawn duh a ni a, item tawp bera awm a ni lo va, item awm zawng zawng kan enchhuah kher a ngai lo, mahse 6 awmnaah hian 4 hi lo awm zawk ta se, item hi kan enchhuah dap a ngai dawn thung a. Chuvangin dinhmun chhe ber (worst case) kan dawnin item awm zat kan zawn a ngai tihna a ni ber a, O(n) tia an dahna chhan pawh a ni. A O pui hi Upper Bound tihna a ni.
Chhiarkawp (Maths) lamah chuan a hnuaia mi ang hian O(n) hi dah a ni thin
T(n) = c * n
T(n) algorithm hnathawh nana a hun hman (running time) sawina a ni a, n hi kan input len zawng (size) sawina a ni thung. c hi constant (danglam ve lo, ngai reng) tia sawi a ni. O(n) hi upper bound tiin an sawi a. Kan item zawn tur zawn nan kan array/list-a item awmzat chiah chiah kan zawn dan step kha kan kaltir a ngai dawn tihna a ni. item 5 lo nei ta la, a tam berah vawi nga endik a ngai dawn tihna. item chu list\array laiah a lo awm a nih chuan vawi 5 kher kha a ngai dawn lo tihna a ni a. Chuvangin c × n tiin a formula dah a ni a. Kan thil zawn nana kan hun hmanral zat tur chu a tam dan bera dahin c × n a ni dawn tihna a ni. Big O-ah chuan a tam dan ber (upper bound) zel hi ngaih pawimawh a nih avangin a formula-ah pawh hetiang zel hian dah thin a ni.
Veilama diagram-ah hian X-axis hi a input a ni a, Y-axis hi execution time a ni. Input (volume of data) a pun zat ang zelin execution time pawh a pung ve a ni. Kan input size hi a leta kan tihpun chuan running time pawh a letin a pung ve dawn tihna a ni. Chuvangin Linear time a hmang tiin an sawi bawk a ni.
O(n) hi list-a thil zawn nan te, data lian tham deuh hlek a linked list-a/array-a element mal te te tlawhchhuah nan te, sorting algorithm – Bubble leh Insertion sort angah te, array-a element belhkhawm (sum) nan te, array-a element average value, minimum leh maximum value zawn nan leh data processing lamah te an hmang ber.
Big O(n2)
Big O(n2)-ah chuan running time hi input size (n) letin a pung zel dawn thung a. Input size hi a letin pung ta se, algorithm step chu atira input size let 4 velin a pung dawn tihna a ni. Chuvangin quadratic time ti te pawhin an sawi thin. Hetiang hi loop chhunga loop (nested loop) algorithm-ah an hmang nasa hle.
Entirnan, kan input size kha 4 lo ni ta se, algorithm chuan upper bound-ah operation 4×4=16 steps a tih a ngai dawn a, input size kha 5 a nih chuan, 5×5 = 25 operations a tih a ngai dawn tihna a nih chu. Hetianga a step hlenchhuah tur a pun chak em avang hian O(n) nena khaikhin chuan a muang bik hle (less efficient) dawn tihna a ni.
T(n) = c × n² + d
T(n) = Running Time
c leh d hi constant a ni a, n hi kan input size sawina a ni. A hma kan sawi tawh ang bawkin upper bound zel Big O-ah chuan kan en vangin constant te hi chu kan enkan dawn a ni. Ti chuan N2 lai hi kan en ber tur chu a ni tihna a ni. Python hmangin entirna lo siam dawn ila
def print_pairs(numbers):
for i in range(len(numbers)):
for j in range(i+1, len(numbers)):
print(numbers[i], numbers[j])
numbers = [1, 2, 3, 4, 5]
print_pairs(numbers)
A chunga code hian number list [1, 2, 3, 4, 5] input a tan a hmang a. Nested loop hmangin numbera inkawp thei awm zawng zawng a chhutchhuak chhuak a ni. Loop hmasa zawk (outer loop) hian lista item position (code-ah hian i anga dah a ni) hi a mal te te-in a en a, position hmasa ber (1 awmna) chu 0 a ni a, 0 position a en zawh chiah khan loop hnuhnung zawk (inner loop) hian lista 0 position zawha awm zawng te kha a indawt danin 1 nen hian a print vek dawn a ni. A lan dan chuan 1 2, 1 3, 1 4, 1 5 pair te hi outer vawi khatnaah chuan a print dawn a ni. He zawh hian outer loop lamah let lehin outer loop hian position 0 zawh chiah mi position 1 atangin a en leh ang, inner loop-in kan sawi tawh angin a bak zawng a endik leh vek ang, lista data awm a zawh thlengin hetiang hian a ti char char mai dawn a ni. Outer loop a kalchhuah apiang khan inner loop tlawhchhuah ngai a lo tlem ve zel a, chuvangin n*(n-1)/2 Maths formula hmanga dah a ni. Hei hi tlem lo sawifiah leh dawn ang hmiang.
Step 1: n-1 kan tih hian pairs kan siam apianga element ngai dahnawn kan duh lovangin n (input size) atangin 1 paih zel tur.
Step 2: n*(n-1): step 1-a kan result hi n original value hmangin kan puntir (multiply) tihna. Hei hi combination awm thei zat hriat nan a ngai a ni.
Step 3: n*(n-1)/2: element pair te hi element pakhat zelah code-a kan hmuh ang hian voi hnih theuh kan chhiar nawn avang leh pair anpui nei awm lo tura kan duh avangin step-2-a kan result hi 2 in kan sem (divide) leh a ngai a ni. Kan example code-a kan hmuh ang hian n*(n-1)/2 chu 5*(5-1)/2 = 10 pairs kan nei dawn tihna a ni.
Big O(n2) kan chian leh zual nan Fibonacci number zawnna function lo siam leh ila:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(4))
O(n log n) Linearithmic Time
Hei hi algorithm hnathawh chak dan tehna dang leh a ni a; a performance lama kan en chuan O(n) leh O(n2) inkara mi a ni. Input size (n) sort tur kan lo nei ta a, O(n)-ah chuan n zat kan sort a ngai tihna a ni a, n log(n) ah chuan hei (n) aia tam hret sort nan step kan mamawh dawn tihna a ni a, chutihrualin O(n2) aia step tlem zawk hmangin kan sort thei tihna a ni thung ang. Entirnan Spell Checker lo hmang ta ila.
A spell checker chuan kan document-a spelling dik lo a check thei a. Check nan hian spelling dik ho (dictionary a ti thin) kha a en hmasak vek phawt a ngai a. Thumal pakhat lek spell dik leh dik loh check turin spelling dik zawng zawng kha a endik vek a ngai dawn a ni. Hetianga a check dawn chuan a check dan steps (algorithm) kha O(n2) a ni dawn a, document lianah phei chuan a hautak hle dawn a ni. Chuvangin hetianga ti lo hian binary search algorithm hmangin check ta se O(log n) time complexity a hmang ang a, a chawk rei lo zawk dawn a ni. Binary search algorithm chuan spelling dik ho kha a laiah then phawkin kan thumal dik leh dik lo lai kha a endik thei a. Kan documenta kan thumal spelling endik tur kha dictionary-a a check apiangin O(log n) time complexity a hmang a, document-a thumal awm zawng zawng check nan O(n) time complexity a hmang thung a, chuvangin n log(n) tia sawi a ni ta a ni. A fiah leh zual nan python code-in lo dah dawn ila:
def spell_checker(word, dictionary):
# convert the dictionary list to a set for faster lookup
dictionary = set(dictionary)
# use binary search to find the word in the dictionary
left = 0
right = len(dictionary) - 1
while left <= right:
middle = (left + right) // 2
if word == dictionary[middle]:
return True # word is in the dictionary
elif word < dictionary[middle]:
right = middle - 1
else:
left = middle + 1
return False # word is not in the dictionary
dictionary = ["hello", "world", "spell", "checker", "example"]
word = "hello"
if spell_checker(word, dictionary):
print(f"{word} is spelled correctly.")
else:
print(f"{word} is spelled incorrectly.")
A chunga example-ah hian dictionary hi sort sa thlap anga ngaih a ni.
O(2n) Exponential Time
“O” hi order of tihna a ni a, algorithm step running time sawi nan (2n) hman a ni a. 2 hi Algorithm-in a hnathawh tur a thawh zawh nana step a mamawh zat sawina a ni a. n hi kan input size sawina a ni thung. Tichuan (2n) chu kan algorithm running time sawina a ni. Kan input size a lo len chhoh khan, algorithm running time pawh a let thawk thawkin a pung zel dawn tihna a ni a, Exponential growth a nih avangin 2 kha a leta a pun chuan 4 a lo ni a, 4 chu a leta a pun leh chuan 8 a ni dawn a ni. Hei hi input size a punin a running a let zela a pun avangin algorithm efficient lo ber pawl a ni. Input size lianah an hmang meuh lo va. An hmanna tlangpui chu Combinatorial search (a chhanna awm zawng zawng zawn nan), Cryptography (key combination awm zawng zawng zawn nan), Backtracking (combination awm thei zawng zawng hmanga thil zawnna leh combination dik lo paih zelna) leh Machine learning (neural network train nan). Python code nen entirna ho te tarlang leh ila:
def all_combinations(arr):
result = [[]]
for x in arr:
result += [combination + [x] for combination in result]
return result
arr = [1, 2, 3]
print(all_combinations(arr))
Code kan en chuan kan list [1, 2, 3] chhunga element hmanga combination siamna a ni a. List thar siamin empty list a chhungah a dah phawt ang a, a mal te te-in combination awm thei a dahlut char char dawn a ni. A list dah luh kha a lian zawngin a thang zel dawn a, chuvangin O(2n) time complexity dan a hmang a ni. Code hi kan run chuan a hnuaia mi ang hian result a nei dawn a ni.
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
O(n!) Factorial Time
O(n!) -ah input pakhat leka a pun pawhin nasa takin computer-in a chawh chhuah nana a hun mamawh pawh a mak makin a pung nghal hluai thei a. Exclamation mark (!) hi factorial sawina a ni a, kan hriat angin Maths operation pakhat a ni a, number eng pawh a aia te number zawng zawng leh a number hmanga kan multiply-a a result lo chhuak kha a factorial tiin kan sawi thin a ni. Entirnan, 5! = 5 × 4 × 3 × 2 × 1 = 120. Chuvangin input chu 5 a nih chuan 4 a nih laia vawi 120-a reiin chawh zawh nan hun a mamawh nasa dawn tihna a nih chu. A hmanna a tam lo hle a, Dawhkan bial-ah mi 5 thutna lo rem dawn ta ila, kan rem theih dan awm zawng zawng chu 120 tihna a ni a, mi paruk an awm a nih chuan 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720 lai seat rem dan a awm thei tihna a ni. Input size lian taka hman chi a ni lo va. Input size te si a pung zawnga kan hman duh chi calculation atan hman tur zawk a ni. Python Code hmangin seat arrangement hi lo siam dawn ta ila:
import itertools
def generate_seating_arrangements(people):
return list(itertools.permutations(people))
people = ["Aremi", "Biaka", "Chami", "David"]
seating_arrangements = generate_seating_arrangements(people)
for i, seating_arrangement in enumerate(seating_arrangements):
print(f"Arrangement {i + 1}: {seating_arrangement}")
Mathematics-ah chuan thil rem dan tur awm thei hrang hrang chawh nan hian permutation (a indawt dana thil inrem dan thlakna) kan hmang a. Khatiang nen khan a in ang chiah a ni. itertools.permutations() hmang hian thut dan indawt hrang hrang kan siamchhuak a, object a nih avangin list-ah kan convert leh a ni. seating arrangements hrang hrang chu kan tlawh chhuak vek (iterate) a, arrangement number nen kan print chhuak leh a ni. Duh chuan a hnuaia mi ang hian recursive function hmangin kan chawk thei bawk a;
def generate_seating_arrangements(people, i, n):
if i == n:
print(people)
else:
for j in range(i, n):
people[i], people[j] = people[j], people[i]
generate_seating_arrangements(people, i+1, n)
people[i], people[j] = people[j], people[i]
people = ["Aremi", "Buatsaiha", "Chhingi", "Dama"]
generate_seating_arrangements(people, 0, len(people))
A hnuaia mi ang hian seat arrangement a chunga mi hian a rawn generate dawn a ni.
['Aremi', 'Buatsaiha', 'Chhingi', 'Dama'] ['Aremi', 'Buatsaiha', 'Dama', 'Chhingi'] ['Aremi', 'Chhingi', 'Buatsaiha', 'Dama'] ['Aremi', 'Chhingi', 'Dama', 'Buatsaiha'] ['Aremi', 'Dama', 'Chhingi', 'Buatsaiha'] ['Aremi', 'Dama', 'Buatsaiha', 'Chhingi'] ['Buatsaiha', 'Aremi', 'Chhingi', 'Dama'] ['Buatsaiha', 'Aremi', 'Dama', 'Chhingi'] ['Buatsaiha', 'Chhingi', 'Aremi', 'Dama'] ['Buatsaiha', 'Chhingi', 'Dama', 'Aremi'] ['Buatsaiha', 'Dama', 'Chhingi', 'Aremi'] ['Buatsaiha', 'Dama', 'Aremi', 'Chhingi'] ['Chhingi', 'Buatsaiha', 'Aremi', 'Dama'] ['Chhingi', 'Buatsaiha', 'Dama', 'Aremi'] ['Chhingi', 'Aremi', 'Buatsaiha', 'Dama'] ['Chhingi', 'Aremi', 'Dama', 'Buatsaiha'] ['Chhingi', 'Dama', 'Aremi', 'Buatsaiha'] ['Chhingi', 'Dama', 'Buatsaiha', 'Aremi'] ['Dama', 'Buatsaiha', 'Chhingi', 'Aremi'] ['Dama', 'Buatsaiha', 'Aremi', 'Chhingi'] ['Dama', 'Chhingi', 'Buatsaiha', 'Aremi'] ['Dama', 'Chhingi', 'Aremi', 'Buatsaiha'] ['Dama', 'Aremi', 'Chhingi', 'Buatsaiha'] ['Dama', 'Aremi', 'Buatsaiha', 'Chhingi']
Ref:
