时间复杂度
时间复杂度用于描述算法的效率, 是衡量算法优劣的重要指标
O(1)
void func(int n){
std::cout << n << std::cout;
}将自变量视作n, n在此情景下为传入的参数
将因变量视作t, t在此情景下为函数执行的指令次数(这个就是时间复杂度)
上述算法中, 无论n是多少, t都为1, 则此算法复杂度记做: O(1)
O(1)复杂度的算法效率不因外界因素而改变
PS: 也称作常量级复杂度, 是最理想的复杂度
O(2n)
略
PS: 其中O(2n)就是呈2倍复杂度增加, 而O(nn)则意为n倍增加
O(n)
void func(int n){
for(int i = 0; i < n; ++i){
std::cout << i << std::endl;
}
}上述算法中 t = n + 1(其中的1为最后一次的失败), 算法复杂度为O(n)
O(n)复杂度的算法效率会因外界因素而改变, 其规律为: 复杂度呈1:1形式增加
PS: O(n)是比较常见的复杂度, 效率一般
O(n^2)/O(n^n)
void func(int n){
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++i){
std::cout << i << std::endl;
}
}
}上述算法中 t = n * n + 1, 记做: O(n^2)
O(n^2)复杂度的算法效率会随外界的影响平方倍变化
同理, 则O(n^n)复杂度的算法效率会随外界的影响呈n次方倍增加
PS: 出现这种复杂度的代码, 则需要考虑优化
O(log n)
要想明白O(log n)时间复杂度, 则先得复习对数
(如果你还没把数学还给数学老师的话, 就不必了)
这东西我也不大说得清楚, 就直接粘贴网上的案例了:
PS: O(log n)的复杂度计算好像不太容易, 一般人还不一定计算得出来…
RET: 总的来说时间复杂度就是一个随着计算数据增加, 算法效率呈何种形式增加的一种规律
了解一下时间复杂度是很有必要的
以后别人问你 你的算法效率如何的时候. 就可以回答: 我的算法时间复杂度是O(1)!
以上经验参照自简书