GO 中切片删除一个元素的复杂度

go 中 a = a[1:] 时间复杂度是 O(n) 还是 O(1)?

我在学 Go 之前是使用 Python。我想知道 Go 中删除一个元素的时间复杂度,如 a = a[1:]。如果是 O(n),是否应该是 deque,如果是 O(1),deque 的作用体现在什么地方?

切片操作是 O(1) 的,它仅仅是改变了切片指向起始指针,底层数组没有改变。一起看下切片的底层结构:

type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

以上就是底层数组的起始地址,len 是切片的长度,cap 是切片的容量。通过一个简单的例子介绍下:

a := make([]int, 10)
fmt.Println(unsafe.Pointer(&a[0]))
a = a[1:]
fmt.Println(unsafe.Pointer(&a[0]))

输出如下:

0xc00019a000
0xc00019a008

看到同样是 a[0],切片前后的地址变化分别是 0xc00019a000 与 0xc00019a008,只是将地址向前移动了一个位长。


最后声明

公司众多岗位正在招聘中,Base 上海和新加坡,P4-P8 岗位全都有。各位大佬有想换工作的,可联系我内推投递简历。

具体 JD 可查看:简历投递。