Array என்பது ஒரே வகையான உறுப்புகளைக் கொண்ட ஒரு தொடர்ச்சியான நினைவக பகுதியாகும், இது 0 இலிருந்து குறியிடப்பட்டுள்ளது. உறுப்புகள் ஒன்றுக்கொன்று அருகில் இருப்பதால், உறுப்பு i இன் முகவரி base + i * elementSize என நேரடியாக கணக்கிடப்படுகிறது, இது O(1) சீரற்ற அணுகலை வழங்குகிறது.
நினைவக தளவமைப்பு
text
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
எடுத்துக்காட்டு
python
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
சிக்கலான தன்மை
| செயல் | நேரம் |
|---|---|
| குறியீடு மூலம் அணுகல் | O(1) |
| தேடல் (வரிசைப்படுத்தப்படாதது) | O(n) |
| சேர்க்க (இயங்குவான) | O(1) மாறுபட்ட |
| செருக/நீக்க முன்னணিতে/நடுவில் | O(n) |
சமரசங்கள்
- வலிமை: வேகமான குறியீட்டு, cache-இயல்புடைய (தரவு தொடர்ச்சியாக உள்ளது), குறைந்த நினைவக மேல்நோக்கு.
- பலவீனங்கள்: நடுவில் செருக/நீக்க O(n); நிலைத்தவ-அளவு arrays வளரசமர்ப்பணிக்கு நகல் தேவை.
இது ஏன் முக்கியமானது
Arrays பெரும்பாலான பிற கட்டமைப்புகளின் அடிப்படை — strings, hash tables, heaps, மற்றும் dynamic lists அனைத்தும் அவற்றின் மீது கட்டமைக்கப்பட்டுள்ளன.
தங்கள் cache locailty பெரும்பாலும் "மெதுவான" Big-O array ஐ "வேகமான" pointer-அடிப்படையிலான கட்டமைப்பைக் கடக்க செய்கிறது நிஜ தரவுப்பதிவுகளில்.