下面这个第二空为什么要填
cx!=front;front!=cx
怎么判断是不是输入了连续两个空格啊
第二空的意思 ,这两个都可以,只不过是交换了顺序
if (cx!=front)
{
}
// 或
if (front!=cx)
{
}
实例1:
void Func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
count++;
int M = 10;
while (M--)
count++;
printf("%d\n", count);
}
Func2 具体执行次数为 2×N+10 ,
用 大O的渐进表示法 表示就是 O(N) 。
实例2:
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++k)
count++;
for (int k = 0; k < N; ++k)
count++;
printf("%d\n", count);
}
Func3 基本操作执行了 M+N 次,
有两个未知数 M 和 N ,
时间复杂度为 O(N+M) 。
实例3:
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; k++)
count++;
printf("%d\n", count);
}
基本操作执行了 10 次,通过推导大O阶方法,
时间复杂度为 O(1)。
实例4:
int strchr(const char* str, char character)
{
int count = 0;
while (*str != '\0')
{
if (*str == character)
return count;
str++;
count++;
}
return -1;
}
这段代码是实现在字符串 str 中找到字符 character 首次出现的位置的下标并返回。
基本操作执行最好 1 次,
最坏 N(N = strlen(str)) 次,
时间复杂度一般看最坏,所以是 O(N) 。
实例5:
void BubbleSort(int* arr, int sz)
{
for (int i = 0; i < sz - 1; i++)
for (int j = 0; j < sz - 1 - i; j++)
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
这段代码就是基本的冒泡排序,它的时间复杂度该怎么算呢?
首先基本操作要执行 N+(N-1)+…+1 次,
也就是 N * (N+1) / 2,
所以时间复杂度就是 O(N2) 。
实例6:
BinarySearch(int * nums, int right, int left, int target)
{
while(left <= right)
{
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
if(nums[mid] > target)
right = mid - 1;
else if(nums[mid] < target)
left = mid + 1;
}
return -1;
}
这是一个简单的二分查找算法。
考虑它最坏的执行次数:
最坏情况是遍历整个有序数组,
设执行次数为 x ,
则有 2x = N,
N 为数组大小,
那么 x = log2N。
所以它的执行次数最坏就是 log2N。
而在实际表示时是忽略它的底数的,
所以它的时间复杂度就是 O(logN) 。
而对于很多题目来说,可能会限制时间复杂度不低于 O(logN) ,这种情况一般就要考虑用到二分查找的算法。
实例7:
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N - 1) * N;
}
这是一个求 N 的阶乘的算法,用的递归实现。
那它执行了多少次呢?
它的递归出口是 N = 1 ,
所以在走到出口之前递归了 N 次;
返回又是一次,所以函数总共执行了 2×N 次;
每次调用函数,函数内部只进行一次基本操作,
所以总基本操作次数就是 2×N×1。
综上,这个算法的时间复杂度就是 O(N)。
时间复杂度是区分一个算法好坏的最直观的量,一般算法效率高低有如下之分:
O(1) > O(logN) > O(N) > O(NlogN) > O(NA) > O(AN) > O(N!)
直观一点就是这样:
循环语句和条件语句需要在需要多次重复执行某些代码的情况下使用,有时需要根据不同的条件选择执行不同的代码块。第二个空需要填写空格(' ')来判断。以下是判断连续两个空格的代码:
string = input("请输入一个字符串:")
count = 0
for i in range(len(string) - 1):
if string[i] == ' ' and string[i+1] == ' ':
count += 1
if count != 0:
print("该字符串中输入了连续的{}个空格。".format(count))
else:
print("该字符串中没有输入连续的两个空格。")
输出结果:
请输入一个字符串:Hello world!
该字符串中输入了连续的2个空格。
注:这是Python代码,请注意与其他语言的语法差异。
cx!=front; 或者 front!=cx; 这两句是等价的,二选一。