时间复杂度的其他问题
先决条件: 渐近符号
时间复杂度: 时间复杂度是算法所需的时间，表示为问题大小的函数。也可以定义为运行一个程序到完成所需的计算机时间。当我们解决一个时间复杂度的问题时，这个定义帮助最大– “它是算法相对于输入大小完成任务的操作数。”
以下是一些时间复杂性的杂七杂八的问题，在不同类型的测验中经常被问到。
1。以下代码的时间复杂度是多少–
C
void function(int n)
{
int i = 1, s = 1;
while (s < n) {
s = s + i;
i++;
}
}
解– 时间复杂度= O(√n)。
解释– 我们可以根据关系 S i = S i-1 + i 来定义‘S’术语，让 k 为程序的迭代总次数
| **i** | **S** | | one | one | | Two | Two | | three | 2 + 2 | | four | 2 + 2 + 3 | | … | … | | k | 2 + 2 + 3 + 4 + ……+ k | 当 S **> =** n 时，则循环将停止在 k 第次迭代， S>= n S = n 2+2+3+4+……+k = n 1+(k *(k+1))/2 = n k2= n k =√n 因此，时间复杂度为 O(√n)。 **2。以下代码的时间复杂度是多少:** ## C++void fun(int n)
{
if (n < 5)
cout << "GeeksforGeeks";
else {
for (int i = 0; i < n; i++) {
cout << i << " ";
}
}
}
void fun(int a, int b)
{
while (a != b) {
if (a > b)
a = a - b;
else
b = b - a;
}
}
void fun(int n)
{
for(int i=0;i*i<n;i++)
cout<<"GeeksforGeeks";
}
**void fun(int n, int x)
{
for (int i = 1; i < n; i = i * x) //or for(int i = n; i >=1; i = i / x)
cout << "GeeksforGeeks;
}**
**void fun(int n)
{
for (int i = 0; i < n / 2; i++)
for (int j = 1; j + n / 2 <= n; j++)
for (int k = 1; k <= n; k = k * 2)
cout << "GeeksforGeeks";
}**
**void fun(int n)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j = j + i)
cout << "GeeksforGeeks";
}**
**void fun(int n)
{
for (int i = 0; i <= n / 3; i++)
for (int j = 1; j <= n; j = j + 4)
cout << "GeeksforGeeks";
}**
**void fun(int n)
{
int i = 1;
while (i < n) {
int j = n;
while (j > 0) {
j = j / 2;
}
i = i * 2;
}
}**
**void fun(int n)
{
int j = 1;
while (j <= n) {
j = j * 2;
}
}**
版权属于：月萌API www.moonapi.com，转载请注明出处
