已知某递归算法的复杂度为:T(n)=2T(n/2)+4,则求解该递归式的解为:()
A.T(n)=O(1)
B.T(n)=O(n)
C.T(n)=O(n^2)
D.T(n)=O(nlogn)
- · 有5位网友选择 D,占比50%
- · 有3位网友选择 C,占比30%
- · 有1位网友选择 B,占比10%
- · 有1位网友选择 A,占比10%
A.T(n)=O(1)
B.T(n)=O(n)
C.T(n)=O(n^2)
D.T(n)=O(nlogn)
A、所有问题都可以写递归程序
B、大部分递归程序可以转换为非递归程序,非递归程序运行速度更快。
C、所有递归程序都可以转换为非递归程序,且递归程序运行速度更快
D、递归程序可以把递归出口写在递归关系的后面
E、尾递归可以转换为循环
已知求一组数据连续若干数和的最大值采用分治方法得到O(nlogn)的时间复杂度,请完成下面分治法求解的代码: /************************************************************************/ /* 分治法 最大和子数组有三种情况: 1)A[1...mid] 2)A[mid+1...N] 3)A[i..mid..j] /************************************************************************/ //find max crossing left and right int Find_Max_Crossing_Subarray(int arr[], int low, int mid, int high) { const int infinite = -9999; int left_sum = infinite; int right_sum = infinite; int max_left = -1, max_right = -1; int sum = 0; //from mid to left; for (int i = mid; i >= low; i --) { sum += arr[i]; if (sum > left_sum) { left_sum = sum; max_left = i; } } sum = 0; //from mid to right for (int j = mid + 1; j <= high; j ++) { sum +="arr[j];" if (sum> right_sum) { right_sum = sum; max_right = j; } } return (left_sum + right_sum); } int Find_Maximum_Subarray(int arr[], int low, int high) { if (high == low) //only one element; return arr[low]; else { int mid = (low + high)/2; int leftSum = Find_Maximum_Subarray(arr, low, mid); int rightSum = Find_Maximum_Subarray(arr, mid+1, high); int crossSum = Find_Max_Crossing_Subarray(arr, low, mid, high); ——————————完成这里的代码—————————————————— } }
A、int tmp=(leftSum>rightSum?leftSum:rightSum; return (tmp>crossSum?tmp:crossSum);
B、if(leftSum>rightSum) { if(leftSum>crossSum)return leftSum; } else { if(rightSum>crossSum)return rightSum; }
C、if(leftSum>rightSum) { if(leftSum>crossSum)return leftSum; else return crossSum; } else { if(rightSum>crossSum)return rightSum; else return crossSum; }
D、if(leftSum>rightSum>crossSum) return leftSum; if(rightSum>leftSum>crossSum) return rightSum; if(crossSum>leftSum>rightSum)return crossSum;
E、if(leftSum>rightSum>crossSum) return leftSum; else if(rightSum>leftSum>crossSum) return rightSum; else if(crossSum>leftSum>rightSum)return crossSum;
F、if(leftSum>rightSum && leftSum>crossSum) return leftSum; if(rightSum>leftSum && rightSum>crossSum) return rightSum; if(crossSum>leftSum && crossSum>rightSum)return crossSum;
已知求一组数据连续若干数和的最大值采用分治方法得到O(nlogn)的时间复杂度,请完成下面分治法求解的代码: /************************************************************************/ /* 分治法 最大和子数组有三种情况: 1)A[1...mid] 2)A[mid+1...N] 3)A[i..mid..j] /************************************************************************/ //find max crossing left and right int Find_Max_Crossing_Subarray(int arr[], int low, int mid, int high) { const int infinite = -9999; int left_sum = infinite; int right_sum = infinite; int max_left = -1, max_right = -1; int sum = 0; //from mid to left; for (int i = mid; i >= low; i --) { sum += arr[i]; if (sum > left_sum) { left_sum = sum; max_left = i; } } sum = 0; //from mid to right for (int j = mid + 1; j <= high; j ++) { sum +="arr[j];" if (sum> right_sum) { right_sum = sum; max_right = j; } } return (left_sum + right_sum); } int Find_Maximum_Subarray(int arr[], int low, int high) { if (high == low) //only one element; return arr[low]; else { int mid = (low + high)/2; int leftSum = Find_Maximum_Subarray(arr, low, mid); int rightSum = Find_Maximum_Subarray(arr, mid+1, high); int crossSum = Find_Max_Crossing_Subarray(arr, low, mid, high); ——————————完成这里的代码—————————————————— } } 注意为了尽量减少答案的多样性,本次编程代码请通过>而不是 <符号进行数据的比较。按照leftsum,rightsum,crosssum的顺序进行比较。>
A、归并
B、简单插入
C、冒泡
D、堆排序
E、树形选择排序
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!