O(log(n))函数的运行时

Question

我在C++中制作了一个AVL树，根据我的所有测试，该树成功地保持了平衡。函数addNode应该在O(log(n((中工作(当n是树中的节点数时(，并且我的实现似乎满足了它。为了验证，我编写了以下测试：

#include "AVLTree.h"
#include "iostream"
#include <chrono>
#include <vector>
#include <random>
#include <algorithm>
#include <memory>
using namespace std;
using namespace std::chrono;
typedef high_resolution_clock Clock;
typedef Clock::time_point ClockTime;
auto ExecutionTime(ClockTime start_time, ClockTime end_time)
{
return duration_cast<nanoseconds>(end_time - start_time).count();
}
#define N 10000000
#define M 100000
int main(){
AVLTree<unsigned long long, unsigned long long> tree; // AVLTree<key type, value type>
ClockTime start_time;
ClockTime end_time;
std::vector<unsigned long long> vector;
for (unsigned long long i=0; i<N; i++) vector.push_back(i);
auto max_time = ExecutionTime(start_time, start_time); // currently zero, will get bigger.
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
shuffle (vector.begin(), vector.end(), std::default_random_engine(seed));
unsigned long long counter = 0;
for (auto i : vector){
start_time = Clock::now();
tree.addNode(i, i);
end_time = Clock::now();
max_time = max(max_time, ExecutionTime(start_time, end_time));
counter++;
if (counter == M){
cout << "Small add: " << max_time << endl;
}
}
cout << "Add: " << max_time << end;
}

因为函数在θ(log(n((中工作，对于足够大的n，T(addNode(<clog(n((T是时间函数(对于某个常数c，如果我们取一个非常紧的，我们可以假设T(addNode(=clog(n(对于足够大的n。这意味着上面的测试应该输出：

Small add: x
Add: (<2x)

对于一些x，大多数时候都是这样，但我也有

Small add: 280100
Add: 14432000

这几乎是100倍大。假设实现是正确的，为什么会发生(这种情况很少发生(？

Answer 1

除了实际的addNode逻辑之外，代码中还有许多内容。在M的情况下，这些事情要多做100倍：

• 将下一个矢量元素复制到i变量(使用const auto&(
• Clock::now()的执行上帝知道它做了多少次调用
• 调用使用模糊时间执行的ExecutionTime函数

现在考虑一下，如果addNode的运行时间在O(log(n))中，那么随着大小的增长，上述操作的影响将变得越来越明显。要对此进行检查，只需注释addNode行并查看结果。