Похожие чаты

For a contiguous data-structure, why is that the access-time is

O(1) and the insertion time (to put data in the middle) is O(n)? I can only see logic in the time remaining the same

Help, please

5 ответов

14 просмотров

because you have to move the all elements from the insertion index one position to make space for it

Contiguous data-structure, we can say it is an array. - Accessing array by given index is O(1), because we can directly read it without enumerating the elements. For example: int a[] = {1, 2, 3, 4}; Accessing a[0], a[1], a[2] and a[3] or even a[n] takes the same time, so it is constant time which is O(1). But inserting data in the middle of array is O(n/2), which is still linear time, we can say O(n) too. This is because we have to shift the elements in order to keep the data well-ordered as we expect. For example: int a[5] = {1, 2, 3, 4}; // a[4] is still unused I want to insert 6 in the middle, so I have to shift 3 and 4 to the right and then put 6 in a[2]. int *p = &a[3]; // shifted index memmove(p, &a[2], sizeof(a) - (sizeof(*a) * 2)); a[2] = 6 The time taken to memmove depends on the number of elements linearly, hence it is O(n). Or precisely O(n/2).

🖖- Автор вопроса
Mmmmm.....
Contiguous data-structure, we can say it is an arr...

🤔 so, let's say: int arr[3]; arr[0] = 3; arr[2] = 4; arr[0] and arr[2] are contiguous, until arr[1] is initialized?

🖖
🤔 so, let's say: int arr[3]; arr[0] = 3; arr[2] =...

as @Mysticial said, the C arrays are contiguos. When you do do int arr[3] you are allocating in the stack 3 consecutive ints.

Похожие вопросы

Карта сайта