英文:
How fast is the cap() function in Golang expressed with Big-O notation?
问题
Golang有len(array)和cap(array)两个函数。前者返回数组/切片的长度（即数组中元素的数量）；据我了解，该函数的时间复杂度为O(1)，即立即返回结果。
cap(array)返回底层数组的容量。然而，这个操作的时间复杂度是O(1)吗？人们可能会认为数组的容量是数组本身具有的一个值，因此可以在O(1)的时间内获取，但我无法确定。
英文:
Golang has both len(array) and cap(array). The former returns the length of the array/slice (that being the amount of elements the array has); as I understand it, that function is O(1); which makes it immediate
cap(array) returns the capacity of the underlying array. However, is that operation O(1)? One would think that the capacity of an array is a value that the array has, and thus could see in O(1) time, but I can't tell for certain
答案1
得分: 6
对于切片（slices），len和cap都只是从切片头部返回相应的值，因此它们是常数时间操作。
对于数组（arrays），len和cap都是在编译时确定的常量。
英文:
For slices, both len and cap simply return the corresponding values from the slice header, so they are constant time operations.
For arrays, both len and cap are compile-time constants.
答案2
得分: 3
内部定义了切片类型的定义如下：
type _slice struct {
// 引用底层元素
elements unsafe.Pointer
// 元素数量和容量
len, cap int
}
对于切片，获取len或cap字段的时间复杂度为O(1)。
在编译程序时，array的len()和cap()会被计算。
对于数组，获取len或cap字段的时间复杂度也是O(1)。
英文:
Internal definition of slice types like:
type _slice struct {
// referencing underlying elements
elements unsafe.Pointer
// number of elements and capacity
len, cap int
}
For slice, it is O(1) to get len or cap field.
len() and cap() of array are evaluated when the program compiling.
For array, it is O(1) to get len or cap field as well.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论