Big-O a thuairiscíonn conas a fhásann am rith nó cuimhne algartam de réir mar a fhásann an méid ionchur n. Gabhann sé tuairim an chás is measa asymptotic, ag déanamh neamhiontas ar thairisigh agus ar théarmaí d'ord níos ísle.
Is cuma linn faoi ráta fáis, ní faoi bhreis céimeanna beachta. Is O(n) go simplí atá i O(2n + 5) toisc, de réir mar a fhásann n, go bhfuil tairisigh agus téarmaí níos lú ag fáil tábhacht níos lú.
| Big-O | Ainm | Sampla |
|---|---|---|
| O(1) | tairiseach | amharc suas san eagar |
| O(log n) | logartamach | cuardach dénártha |
| O(n) | líneach | liosta a scanadh |
| O(n log n) | línearthach | cnuasú a scagadh |
| O(n²) | cearnach | lúb neadaithe |
| O(2ⁿ) | fréimheach | fo-thacair dhúchóirithe |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Cuireann Big-O tairisigh i bhfolach: is féidir le algartam O(n) le tairisigh ollmhór a dhéanamh níos measa ná O(n log n) ar ionchur beag. Cuir san áireamh freisin an chastacht spáis, ní hamháin am.
Ligíonn Big-O duit algartaim a chur i gcomparáid gan iad a rith nó bheith buartha faoin bhardún crua.
Tuarann sé cé na réitigh a mhaireann nuair a fhásann ionchur ó na céadta go na milliúin — an difríochtaíocht idir gné a bheirteann ar scála agus ceann a bhíonn ag fágáil amach.
Is é an briathra gach innealtóir a úsáideann sé chun a smaoineamh ar dhul i bhfeidhm.