我对复杂性度量还很陌生，请耐心等待。
我理解以下复杂性示例:
O(n) - 线性时间
示例:
std::vector<int> MyV={1,4,6,2,9};
std::for_each(MyV.begin(), MyV.end(), [](int e1, int e1){return e1<e2;});
//I.e. n of operations based on the number of elements
O(1) - 常数时间
例子:
for(int i=5; i--;)
{
//Do Stuff
}
//i.e. n of operations will be 5
O(n2) - 二次时间
例子:
std::vector<int> MyVec_A={1,2,3,4,5};
std::vector<int> MyVec_B={1,2,3};
for(int i=MyVec_A; i--;)
{
for(int x=MyVec_B; x--;)
{
//Do Stuff
}
}
上面的例子是否正确？
如果没有，您能否提供一些关于我如何更正示例的指示？
我也不确定对数时间 O(log n)，一个例子真的很有帮助吗？
你说你最后一个例子是 O(n2)，但是 n 是多少？？？这就是你应该问自己的问题。它通常是循环运行的 vector 的大小。
最简单的情况是:
std::vector<int> MyVec_A = {1, 2, 3, 4, 5};
std::vector<int> MyVec_B = {1, 2, 3, 4, 5};
for(int i = MyVec_A; i--;)
{
for(int x = MyVec_B; x--;)
{
// Do Stuff that are of negligible complexity
}
}
现在自信地说，这个例子的复杂度是:O(n2)，其中n是MyVec_A的大小(或等效于 MyVec_B)。
现在，在您的具体示例中， vector 的长度不同，因此您需要更改现有内容。假设 MyVec_A 的大小为 n 并且``MyVec_B的大小为m`，那么这个双循环的时间复杂度为:
O(n*m)
我希望很清楚，当 vector 大小相同时，如我的示例所示，n = m 并且复杂度变为 O(n * m) = O(n * n) = O(n2).
对数复杂度的hello world就是二分查找法。
给定一个整数数组，您需要找到一个来自用户输入的数字。您可以线性搜索整个数组(O(n) 复杂度，其中 n 是数组的大小)，或者，如果数组是排序，您可以找到O(logn) 中的元素，通过使用 Binary search algorithm .我什至有一个例子 Binary Search (C++) .
顺便说一句，学会问一个问题(或与一个问题紧密相关的子问题)。