php公司网站系统,在哪里申请网站,做积分网站,设计师证书报考条件复杂度分析#xff1a; 时间复杂度#xff08;算法中的基本操作的执行次数#xff09;#xff1b; 空间复杂度。 时间复杂度#xff1a; 实际上我们计算时间复杂度时#xff0c;我们其实并不需要计算准确的执行次数#xff0c;只需要大概的执行次数#xff0c;因此我们…复杂度分析 时间复杂度算法中的基本操作的执行次数 空间复杂度。 时间复杂度 实际上我们计算时间复杂度时我们其实并不需要计算准确的执行次数只需要大概的执行次数因此我们在这里使用大O的渐进表示法。常见的时间复杂度O1 ON² ON OlogN。
大O符号
是用于描述函数渐进行为的数学符号。
推导大O阶方法
1.用常数1取代运行时间中的所有加法常数
例
计算下面代码的时间复杂度
void f(int N)
{int count 0;for(int k 0; k 100; k){count;}
}
答案O1
注确定的常数次都是O1。
2.在修改后的运行次数函数中只保留最高阶项
例
计算下面代码的时间复杂度
void f(int N)
{int count 0;for (int i 0; i N; i){for (int j 0; j N; j){count;}}for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d, count);
}
答案ON²
注准确的执行次数N² 2 * N 10 随着N的增大这个表达式中N²对结果的影响最大
3.若最高阶项存在且不是1则去除与这个项相乘的常数。得到的结果就是大O阶。
例
计算下面代码的时间复杂度
void f(int N)
{int count 0;for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d, count);
}
答案ON
特殊情况
例一
计算下面代码的时间复杂度
void f(int N, int M)
{int count 0;for (int k 0; k N; k){count;}for (int k 0; k M; k){count;}
}
答案OM N
注假如给了条件M远大于N答案是OMM和N差不多大OM或ON。
例二
计算下面代码的时间复杂度
const char* s(const char* str, char cha)
{while (*str ! \0){if (*str cha){return str;}str;}return NULL;
}
假设字符串长度是N。
答案ON
注有些算法的时间复杂度存在最好平均最坏情况 最坏ON 平均ON/2 最好O1
在实际中一般情况关注的是算法的最坏运行情况。
例三
计算下面代码的时间复杂度
void B(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (!exchange){break;}}
}
答案ON²
注第一趟冒泡N 第二趟冒泡N - 1 ........ 第N趟1
以上是个等差数列所以准确的次数是N1*N/2
时间复杂度为ON²
例四
计算下面代码的时间复杂度
int B(int* a, int n, int x)
{assert(a);int begin 0;int end n;while (begin end){int mid begin ((end - begin) 1);if (a[mid] x){begin mid 1;}else if (a[mid] x){end mid;}else{return mid;}}return - 1;
}
答案OlogN
注假设找了X次
2的X的平方 N
XlogN
因为有很多地方不好写底数所以一般省略简写成logN。
例五
计算下面代码的时间复杂度
long long f(size_t N)
{return N 2 ? N : f(N - 1) * N;
}
答案ON²
注递归调用了N次每次递归运算--》O1
整体就是ON。
