gpt4 book ai didi

c++ - 列表类型的binary_search函数的时间复杂度是多少

转载 作者:行者123 更新时间:2023-12-01 14:39:33 24 4
gpt4 key购买 nike

是O(n)还是O(logn)?

  list< int > myList = { 2, 6, 12, 13, 15, 18, 20};    
cout << binary_search(myList.begin(), myList.end(), 20) ;

最佳答案

Complexity

The number of comparisons performed is logarithmic in the distance between first and last (At most log2(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, number of iterator increments is linear.

(c) cppreference

std::list迭代器不是随机访问迭代器(它们是转发迭代器),因此复杂度为 O(n)

关于c++ - 列表类型的binary_search函数的时间复杂度是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61286953/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com