算法学习1

一.时间复杂度

列如：

//长度为n的整型数组
int arr[n];

//循环1
for(int i = 0 ;i < n; i++)
{
for(int j = i;j < n;j++)
{
cout << arr[i] << endl;
cout << arr[j] << endl;
}
}

在循环中，数组中的元素在不断重复的被查看，其元素总共被查看的算式为aN²+bN+c，而时间复杂度就是只要N²其他的都可以忽略

注意：
当俩个算法的时间复杂度相同时，则需要让算法添加数据进行实际运行来进行比较

二.排序

1.选择排序

for(int i=1;i<n;i++){
int Min=i;
for(int j=i+1;j<=n;j++){
if(a[j]<a[Min]){
Min=j;
}
}
swap(a[i],a[Min]);
}

原理即使先将第 i 元素和其之后的每个元素进行比较，直到为当前最大（或最小），然后将 i 加一，接着进行下一轮比较

2.冒泡排序

for (i = 0; i < n - 1; i++) {
        // 设定一个标记，判断本次遍历是否进行了交换
        bool swapped = false;
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                
                // 表示进行了交换
                swapped = true;
            }
        }
        
        // 如果这一轮没有交换，说明数组已经排序好了
        if (swapped == false)
            break;
    }

第一个元素与对相邻的元素进行比较，并交换，然后又从下一个元素开始与其下一个相邻的元素进行比较，直到比较到最后一个，又开始从第一个开始进行新一轮比较，直到比较到上轮比较最后一个元素的前一个结束

三.异或交换

其可以看作是不进位的相加

int a = 2,b = 3;
a = a ^ b;
b = a ^ b;
a = a ^ b;
//a = 3，b = 2完成了交换

异或算法具有交换律和结合律

可以用于解决以下问题
问题一：
当数组中只有一个数出现的次数为奇数，其他的为偶数

方法：
将数组中的每个元素都进行异或算法，最后的结果就是出现奇数的值；

原因是出现偶数的值进行异或之后都变为了0；

问题二：
当数组中有两个数出现的次数为奇数，其他的为偶数

方法：
首先将数组中的每个元素都进行异或算法，最后的结果为两个奇数的异或；
然后在该异或中找到二进制位上位1的位置，其含义是在该位置上两个奇数的值不相同；
接下来将数组分为两部分，一部分为该位置上为1的集合，另一部分为该位置上位0的集合；
对其中的一个集合中的所有元素进行异或计算，则可以得出其中一个值；
最后将得出的值与两个数的异或值再一次进行异或，就可以得出另一个值；

如何选取出其中的1：

//eor为两个奇数的异或，用于提取出一个数中最右侧的1
eor & (~eor + 1);

注：下图中第二行为取反，最后一行为结果

原文地址：https://blog.csdn.net/qq_65818377/article/details/142399293

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！