我试图了解是否有任何替代蛮力算法(或轻微的改进/最坏的性能比幼稚的蛮力算法)仍然将导致O(N^2)的时间复杂性和O(1)辅助空间。
这是我的蛮力伪码:
procedure distinct(Input: array)
for i=0 to i < length of array
for j=i+1 to j < length of array
if array[i] ==
考虑使用二进制搜索树对n个元素的列表进行排序的以下算法:
initialise t to be an empty binary search tree
for each element x in the list,
add x to t
while t is not empty,
remove and print the smallest element of t
如果使用以下方式实现树,则此算法的最坏时间复杂度是多少:
a)一个普通的二叉搜索树?
b) AVL树?
我的解决方案:我认为的解决方案,对于AVL树: O(Log N),对于BST,它将是O(N)
因此,当我在处理编程竞赛(ACM ICPC等)中的一些实践问题时,人们经常可以采用O(N^2)解决方案,甚至更糟,并使用堆(C++中的priority_queue)或use来降低复杂性。(作为某种优化,在注意到模式中的“某些东西”之后)
例如,在“滑动窗口最大值”问题中,这几乎是:
For each window of size K in an array of size N, compute the maximum.
这里有一个简单的O(NK)算法,一个相当简单的O(nlogn)解决方案(甚至我都可以看到,使用一个堆)和一个O(N)解决方案,使用一个双端队列。
这些原则似乎是基于“丢弃”无用
所以我有个任务。我得到了n个数字和m个区间,我需要计算出第i个区间中有多少个数字。我已经写了一些复杂度为O(n*m)的代码,尽管我需要对其进行更多的优化。有什么帮助吗?代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
cout.tie(0);
int n,m,temp,temp1;
vector <pair<int, int>> uogienes;
v