Big O Notation: What A-Level CS Actually Expects

Mae Big O notation yn ymddangos ar bob prif spec gwyddoniaeth gyfrifiadurol A-level (AQA, OCR, Edexcel) ac mae'n drysu llawer o fyfyrwyr nid oherwydd bod y mathemateg yn anodd, ond oherwydd na welant ef wedi'i gysylltu â cod gwirioneddol. Mae hwn yn rehediad ymarferol trwy'r hyn sydd angen i chi ei wybod a sut i ateb cwestiynau arholiad arno heb lond ceg o lol.

Beth mae Big O yn ei fesur mewn gwirionedd

Mae Big O yn disgrifio sut mae amser rhedeg (neu ddefnydd cof) algorithm yn tyfu wrth i faint y mewnbwn, a elwir yn n fel arfer, ddod yn fwy. Nid mesuriad stopwatch mewn eiliadau yw. Mae'n ffordd o ddisgrifio cyfraddiad twf fel y gallwch chi gymharu algorithmau annibynnol o galedwedd.

Pan fyddwch chi'n ysgrifennu O(n), rydych chi'n dweud: os ydw i'n dyblu'r mewnbwn, mae'r gwaith yn fras-ddyblu. Mae O(n²) yn golygu bod dyblu'r mewnbwn yn fras-bedryplygu'r gwaith. Y berthynas honno yw'r hyn y mae arholwyr eisiau i chi ei nodi, nid cyfrif gweithrediadau union.

Y cymhlethdodau sydd angen i chi eu gwybod yn dda

Ar gyfer A-level, dyma'r rhai sy'n ymddangos dro ar ôl tro:

• O(1) – amser cysonol. Cael mynediad at elfen array trwy fynegeydd: arr[5]. Nid yw'n bwysig pa mor fawr yw'r array.
• O(log n) – logarithmig. Chwilio deuaidd ar restr drefniadol. Mae pob cam yn haneru'r gofod chwilio sy'n weddill.
• O(n) – llinol. Cylch sengl trwy restr, fel chwilio llinol sy'n gwirio pob eitem unwaith.
• O(n log n) – llinearithmig. Mae merge sort a quicksort (achos cyfartalog) yn glanio yma.
• O(n²) – cwadratig. Cylchau nythu dros yr un data, sy'n union yr hyn y mae bubble sort, insertion sort, a selection sort yn ei wneud.
• O(2ⁿ) – esbonyddol. Fibonacci ailadroddus naïf heb memoriseiddio. Yn mynd yn hyll yn gyflym.

Dylech chi allu edrych ar ffug-godiad a dweud pa un o'r rhain ydyw ar yr olwg gyntaf, oherwydd dyna'r hyn sy'n cael ei brofi yn bennaf.

Darllen cod am gymhlethdod

Y dull sy'n gweithio bob tro: cyfrif y cylchau a gweld sut maent yn cysylltu ag n.

# O(n) - un cylch, un basiad
for i in range(n):
    print(i)

# O(n^2) - cylch nythu, y ddau wedi'u clymu i n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - mae'r gofod chwilio yn haneru pob iteriad
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

Mae cylch nythu lle mae amrediad y cylch mewnol yn dibynnu ar n yn dal i fod O(n²), hyd yn oed os yw'n edrych ychydig yn wahanol (fel for j in range(i) yn lle for j in range(n) — mae hynny'n dal i fod yn gwadratig yn gyffredinol, dim ond gyda gwahaniaeth ffactor cysonol).

Gwyliadwriaeth ar gyfer cylchau nad ydynt yn dibynnu ar n o gwbl. Cylch sy'n rhedeg 10 gwaith bob amser ni waeth beth yw maint y mewnbwn yw O(1), hyd yn oed os oes cylch yn bresennol. Hoffir gan arholwyr slipo hwn i mewn.

Algorithmau didoli cyffredin a'u Big O

Mae hwn yn bwnc arholiad ffefryn oherwydd ei fod yn uno dwy spec yr un pryd: algorithmau didoli a gymhlethdod.

Algorithm	Achos gorau	Achos gwaethaf
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

Mae cysondeb merge sort (yr un gymhlethdod achos gorau a gwaethaf) yn werth ei grybwyll yn benodol os yw cwestiwn yn gofyn pam y byddech chi'n ei ddewis dros bubble sort ar gyfer setiau data mawr. Achos gorau bubble sort o O(n) yn unig yn berthnasol gydag optimeiddiad allanfa gynnar pan nad oes dim newidiadau yn digwydd mewn basiad — crybwyllwch y manylion hwnnw os ydych chi'n ei godi, gan fod rhai bwrdd arholiad yn disgwyl hynny.

Lle mae myfyrwyr yn colli marciau

Y un mwyaf: ysgrifennu