#include <iostream> #include <iomanip> #include <bits/stdc++.h> using namespace std; int main() { int j; char a[103];/*//原输入 ,b[100]//无空格 ,c[100]//纯字母 ,d[100]//去重后排序 ;*///一直改都超限就去掉一些不必要的数组 while(gets(a)) { j=0; for(int i=0;i<strlen(a);i++) { if(a[i]!=' ') { printf("%c",a[i]); } if(a[i]>='a'&&a[i]<='z') { j++; printf(" "); } if(a[i]!=' '&&(a[i]<97||a[i]>122)&&!(a[i]=='-'&&a[i+1]=='>')&&!(a[i]=='<'&&a[i+1]=='-'&&a[i+2]=='>')&&!(a[i-1]=='<'&&a[i]=='-'&&a[i+1]=='>')&&!(a[i]=='|'&&a[i+1]=='|')&&!(a[i-2]=='<'&&a[i]=='-'&&a[i+1]=='>')) {//最后一个条件自己做的时候没有想到，到网上查才发现< ->的情况； printf(" "); } } printf("\n"); ///////////////////////////////////////////////////////////////////////去重 for(int i=0;i<strlen(a);i++) { for(int k=0;k<strlen(a);k++) { if(i!=k&&a[i]==a[k]&&a[i]<='z'&&a[i]>='a') { a[i]=' '; j--; } } } ///////////////////////////////////////////////冒泡排序 for(int i = 0;i <strlen(a);i++) //采用双重循环 { for(int k = 0;k <strlen(a);k++) { if(a[i] > a[k]&&i<k&&a[i]<='z'&&a[i]>='a'&&a[k]<='z'&&a[k]>='a') { char temp=a[i]; a[i]=a[k]; a[k]=temp; } } } for(int k=0;k<strlen(a);k++) if(a[k]<='z'&&a[k]>='a') printf("%c ",a[k]); printf("\n"); // cout<<j<<endl; //////////////////////////////////////////////真值部分 for(int i=1;i<=pow(2,j);i++) { int e=pow(2,j); int f=j-1; int g=(i-1)%e; if(i==pow(2,j)+1) g=pow(2,j); for(int k=0;k<strlen(a);k++){ if(a[k]<='z'&&a[k]>='a') { int h=pow(2,f); if(h==1) { int l=i/h; if((l%2==0)) printf("0 "); else printf("1 "); } else //if(h!=0) { int l=g/h; if((l%2==0)) printf("1 "); else printf("0 "); } f--; } } printf("\n"); } } return 0; } 时间复杂度和空间复杂度
在分析这段代码的时间复杂度和空间复杂度之前，我们先来理解代码的主要功能。代码的主要目的是处理输入的字符串，包括去除空格、字母去重、排序以及生成真值表。
空间复杂度分析
-
字符数组：
char a[103],char b[100],char c[100],char d[100]。这些数组的大小是固定的，因此它们对空间复杂度的贡献是常数级别的。 -
整数数组：
int number[26]。这个数组的大小也是固定的，对空间复杂度的贡献同样是常数级别的。 -
向量：
vector<int> vec;。这个数据结构的大小取决于输入字符串中字母的数量，因此它对空间复杂度的贡献是线性的，即 O(n)，其中 n 是输入字符串的长度。
时间复杂度分析
-
第一个循环：处理输入字符串，去除空格和特殊字符。这个循环的时间复杂度是 O(n)，其中 n 是输入字符串的长度。
-
去重循环：双重循环用于去除重复的字母。最坏情况下，这个循环的时间复杂度是 O(n^2)，因为对于每个字符，都需要检查它是否与数组中的其他字符重复。
-
冒泡排序：双重循环用于对字母进行排序。这个排序算法的时间复杂度是 O(n^2)，其中 n 是字符串中字母的数量。
-
真值表生成：这部分代码使用了嵌套循环和幂运算来生成真值表。最内层循环的时间复杂度是 O(j)，其中 j 是字母的数量。由于 j 可能小于 n，但具体取决于输入，我们可以认为这部分的时间复杂度是 O(n * 2^j)。
综合分析
-
空间复杂度：由于使用了固定大小的数组和线性大小的向量，空间复杂度主要由向量决定，可以认为是 O(n)。
-
时间复杂度：代码中存在 O(n^2) 的去重和排序操作，以及 O(n * 2^j) 的真值表生成。在最坏的情况下，时间复杂度由真值表生成部分决定，即 O(n * 2^j)。然而，如果 j 远小于 n，排序和去重操作可能会成为主要的时间复杂度因素。
需要注意的是，这段代码中使用了 gets() 函数，这是一个不安全的函数，因为它可能导致缓冲区溢出。在现代 C++ 编程中，推荐使用 fgets() 或其他更安全的输入方法。此外，代码中还存在一些未使用的数组和变量，这可能会影响性能和可读性。25678。