时间戳

首页 > 解决方案 > 这三种基于时间复杂度的算法有什么区别？

c++ - 这三种基于时间复杂度的算法有什么区别？

问题描述

所有这三种算法只是简单地计算大小为 10 的数组的总和。在这里，我对时间复杂度和我想要哪个更快。你能帮助我，以便我能很好地理解时间复杂度。

算法1
在算法 1 中，循环运行 10 次。

int arr[10] = {1, 2, 3, 4, 5 ,6 ,7, 8, 9, 10};
int sum = 0;
int size = 10;
int i = 0;
for(int i = 0; i < size; i++){
    sum += arr[i];
}
cout<<sum;

算法2
在算法 2 中，循环运行的数组大小是数组大小的一半，但在每次迭代中，它都会执行双倍的操作。减少迭代次数会使算法更快吗？

int arr[10] = {1, 2, 3, 4, 5 ,6 ,7, 8, 9, 10};
int sum = 0;
int size = 10;
int i = 0;
for(int i = 0; i < size/2; i++){
    sum += arr[i];
    sum += arr[size-1-i];
}
cout<<sum;

算法 3

int arr[10] = {1, 2, 3, 4, 5 ,6 ,7, 8, 9, 10};
int sum = 0;
int size = 10;
int i = 0;

for(i = 0; i < size/2; i++){
    sum += arr[i];
}

for(int j = i; j < size; j++){
    sum += arr[j];
}
cout<<sum;

标签： c++algorithmbig-o

解决方案

简短的回答：它们都具有相同的时间复杂度，O(n)。

就时间复杂度（大哦符号）而言，它们都是相同的。

第一个执行(one operation * size of array)的是O(n)复杂性（考虑n到数组的大小）。
第二个执行(2 operations * (size of array) / 2)which is O(2 * n / 2)， which is 也O(n)。
第三个执行(1 operation * size of array / 2 + 1 operation * size of array / 2)，也是O(n)。

这 3 种算法在实时执行上可能略有不同，但这与缓存优化和相关主题有关。

推荐阅读