英文:
Two number sum algorithm
问题
下面的算法的时间复杂度是O(log(n))，但我只是好奇for循环的时间复杂度是多少？
func TwoNumberSum(array[] int, target int)[] int {
sort.Ints(array)
left, right: = 0, len(array) - 1
for left < right && left >= 0 && right < len(array) {
if array[left] + array[right] == target {
return [] int {
array[left], array[right]
}
} else if array[left] + array[right] < target {
left += 1
} else {
right -= 1
}
}
return [] int {}
}
请注意，我只提供翻译服务，不会回答关于翻译内容的问题。
英文:
Time complexity of an algorithm below is O(log(n)), but I'm just curious what is time complexity of the for loop?
func TwoNumberSum(array[] int, target int)[] int {
sort.Ints(array)
left, right: = 0, len(array) - 1
for left < right && left >= 0 && right < len(array) {
if array[left] + array[right] == target {
return [] int {
array[left], array[right]
}
} else if array[left] + array[right] < target {
left += 1
} else {
right -= 1
}
}
return [] int {}
}
答案1
得分: 3
以下是翻译好的内容：
下面算法的时间复杂度是O(log(n))
这个说法是不正确的。对于input = [1,2,3,4,5]和target = 9，left将遍历整个数组。整个for循环以及整个算法的复杂度都是O(n)。
编辑：我刚刚注意到额外的sort()调用。排序将使算法的复杂度变为O(nlogn)。
英文:
> Time complexity of an algorithm below is O(log(n))
The claim is incorrect. For input = [1,2,3,4,5] and target = 9, left will traverse the entire array. The complexity of the for loop, and for the entire algorithm, is O(n).
Edit: I just noticed the extra sort() call. Sorting will make the algorithm's complexity O(nlogn).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论