案例
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; set<int> st; void init() { st.clear(); for(int i=0;i<1000000;i++) { st.insert(i+1); } } void foo() { long i; for (i=0;i<1000000000;i++) { long a= 0; a = a+1; } } void foo_set_count() { for(int i=0;i<1000000;i++) { st.count(i+1); } } void test() { double dur; clock_t start,end; start = clock(); // do something... // foo(); foo_set_count(); end = clock(); dur = double(end - start); printf("Use Time: %f\n",(dur/CLOCKS_PER_SEC)); } int main() { init(); test(); return 0; }
结果
解析
clock() 函数返回从 “开启这个程序进程” 到 “程序中调用 clock() 函数” 时之间的 CPU 时钟计时单元（clock tick）数，在MSDN 中称之为挂钟时间（wal-clock）常量 CLOCKS_PER_SEC，它用来表示一秒钟会有多少个时钟计时单元。并且用 clock_t 方法来做时间差的优点：支持 Linux + Windows 系统。
需要测试哪个方法就把该方法放到时间差变量的中间位置，千万不要把之前的预备工作也放入在内，以免结果有误差。而且最好不要单个测试，最好弄个 for 循环来多跑 N 次（最后的结果除以 N），以免出现偶然性。
一般情况，1s 可以跑 10^8 次数量级单位，OJ 评测比本机应该要更快个（1~10）倍之间不等。
执行一次 st.count() 方法：0.669 * 10^8 / 10^6 == 66.9 数量级单位。log(2,10^6) (下2，上10^6) ==19.93。又因为 OJ 与本机之间有几倍的误差，所以可以看为这个结果是有效的。所以 set.count() 属于 O(logn) 级别。
