下列哪个函数是O(N)的? A. (logN) 2 B. (NlogN)/1000 C. N(logN) 2 D. N 2 /1000
时间: 2024-03-30 09:38:30 浏览: 57
函数的时间复杂度O(N)表示随着问题规模N的增加,算法的运行时间线性增长。根据这个定义,我们可以看出,选项D是O(N)的,因为N平方除以常数1000最终还是N的量级。而选项A和C是O((logN)²)和O((logN)²*N)的,它们的复杂度都小于O(N)。选项B是O(NlogN)的,虽然它也是随着N的增加而增加,但增长速度比O(N)要快,因此也不是答案。因此,选项D是正确答案。
相关问题
利用主定理说明以下时间函数的复杂度: T(n) = 9T(n/3) + n ;T(n) = T(2n/3) + 1 ;T(n) = 3T(n/4) + nlogn
对于第一个时间函数 T(n) = 9T(n/3) + n,我们可以使用主定理来判断其时间复杂度。其中,a = 9,b = 3,f(n) = n。根据主定理,这个时间函数的复杂度为 O(nlogb(a)) = O(nlog3(9)),即 O(n2.177)。
对于第二个时间函数 T(n) = T(2n/3) + 1,同样可以使用主定理来判断其时间复杂度。其中,a = 1,b = 3/2,f(n) = 1。根据主定理,这个时间函数的复杂度为 O(logb(a)) = O(log3/2(1)),即 O(0),也就是常量时间复杂度。
对于第三个时间函数 T(n) = 3T(n/4) + nlogn,同样可以使用主定理来判断其时间复杂度。其中,a = 3,b = 4,f(n) = nlogn。根据主定理,这个时间函数的复杂度为 O(nlogb(a)) = O(nlog4(3)),即 O(n1.26logn)。
1. 二分查找:在N个无序整数里面查找M个指定整数
好的,针对您的问题,我可以给出以下的二分查找算法实现:
```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> binary_search(vector<int>& nums, vector<int>& targets) {
vector<int> res;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < targets.size(); ++i) {
int left = 0, right = n - 1;
bool flag = false;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == targets[i]) {
res.push_back(mid);
flag = true;
break;
} else if (nums[mid] < targets[i]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (!flag) {
res.push_back(-1);
}
}
return res;
}
int main() {
vector<int> nums = {3, 1, 4, 2, 5};
vector<int> targets = {1, 3, 6};
vector<int> res = binary_search(nums, targets);
for (int i = 0; i < res.size(); ++i) {
cout << res[i] << " ";
}
cout << endl;
return 0;
}
```
上述代码使用了 STL 库中的 sort 函数对原始数组进行排序,时间复杂度为 O(NlogN);然后使用二分查找算法,时间复杂度为 O(MlogN),其中 M 表示指定整数的个数。因此,总时间复杂度为 O((M+N)logN)。
另外,上述代码中的 res 数组中保存了每个指定整数在原始数组中的下标,如果原始数组中不存在对应的指定整数,则返回 -1。