给定一个数组。如何在固定时间内求出索引区间(i, j)中元素的和?你可以使用额外的空间。
示例:
答:3 2 4 7 1 -2 8 0 -4 2 1 5 6 -1
长度= 14
int getsum(int* arr, int i, int j, int len);
// suppose int array "arr" is initialized here
int sum = getsum(arr, 2, 5, 14);
在固定时间内,sum应为10。
我编写这个函数是为了找到数组中第二大元素,但我对它的时间复杂性有一些疑问。如果条件有θ(1)还是增加了递归调用的时间复杂度?
从实验的角度看,它不应大于最大的最大元素,具有分而治之的策略时间复杂度。
int secondmax(int arr[], int first , int last){
if(first+1==last) return arr[first];
int mid= first +(last-first)/2;
int left = secondmax(arr, first, mid);
int right = secondmax(arr, mid,
今天我在HackerRank上练习一个算法练习:
我决定用两种方法解决这个问题。
第一种算法,基于弗洛伊德的算法:
/*
Insert Node at the end of a linked list
head pointer input could be NULL as well for empty list
Node is defined as
class Node {
int data;
Node next;
}
*/
int FindMergeNode(Node headA, Node headB) {
// Complete thi
Kruskal的算法如下:
MST-KRUSKAL(G,w)
1. A={}
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight w
6. if FIND-SET(u)!=FIND-SET(v)
7. A=A U {(u,v)}
8. Union
假设我们被要求计数并打印给定字符串中每个字符的出现情况。为了简单起见,字符串只有小写字母。我编写了这两个函数,我想知道哪一个在Java中更有效/更可取。
函数1:
private void countAndPrintArray1(String str){
int[] a = new int[26];
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int index = c - 'a';
我有个问题.我有个算法
procedure summation(A[1...n])
s=0
for i= 1 to n do
j=min{max{i,A[i],n^3}
s= s + j
return s
我想用渐近表示法θ在这个算法中求出最小和最大输出。对怎么做有什么想法吗?我要看什么算法才能理解它的复杂性?
我设计了一个算法,将10的幂转换为二进制,假设n是2的幂。我使用高斯方法来利用这个很好的方法的快速运行时间。为此,我将n除以2,并将其发送到Gauess方法,如下所示:
changetoBinary(n)
if n=1
return binary of 10 which is 1010
else
return gauess(n/2,n/2)
很明显,猜测方法将首先分裂,然后征服,然后合并。最后,我们将数字更改为二进制。现在我的问题是关于算法的运行时间:我的理解是,由于猜测运行时间是θ(n^log3(Base2)),我们可以说这个算法的运行时间也是相同的,因为大多数工作都是由Gue
通常,当分析算法的运行时间时,我处理的是影响运行时间的单个输入。我正在尝试理解当有2个或更多的输入影响运行时间时,如何表示T(n)。 例如,在最坏情况下的线性搜索中: function LinearSearch(arr, N, x)
for (i = 0; i < N; i++) ---> C1*N + C2
if arr[i] = x ---> C3*N
return true
return false --->
对称差分有两个定义在数学上是等价的,我有三个函数可以构成对称差分,但当我试图用这两个定义求出总复杂度时,我得到了两个不同的表达式。
这些是功能的运行时:
int minus(int a[], int b[]) //O(alogb)//here a and b denotes the size of the arrays
int union(int a[], int b[]) //O(a+b)
int intersect(int a[], int b[])//O(alogb)//a is the smaller array WLOG
使用对称差分的第一个定义(联合b)-(相交b):
/*
Returns true is the two strings are permutations of each other.
Time Complexity; O(nlog n) -> because of the java utils array sort
Space Complexity; O(1)
*/
public boolean isPermutationOptimized(String one, String two) {
if (one.length() != two.length()) {
return
我对big-o还很陌生,我想弄清楚这一小段代码的大o运行时间是多少。我知道通常情况下,如果有,但是整个数组的事情会改变什么吗?我很困惑,所以任何一点的输入都是很好的。提前感谢!
public apple(int n)
{
int n = 0;
int apple = 0;
a = apple + n;
}
这可能是已涵盖的理由,但我尚未找到我能够理解的解释。我可能很快就会感到尴尬。
例如,我试图使用以下大O表示法求出数量级:
count = 0;
for (i = 1; i <= N; i++)
count++;
我从哪里开始发现什么定义了震级?我的数学能力相对较差,尽管我尝试了一些资源,但还没有找到能解释一段代码如何转化为代数方程的东西。坦率地说,我甚至无法猜测,关于这个循环的大O效率是什么。
我的代码是下面的leetcode 53.Maximum Subarray,但是没有传递one test case。 如何修复当前代码以防止超过时间限制? class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = nums[0]
array_len = len(nums)
for
请考虑下面的合并排序算法。在这里,我们从一个除法部分开始,它将数组分成两半,并分别对每一半进行递归操作。为了降低复杂度,我忽略了算法的合并部分。
function mergeSort(unsortedArray)
{
let midpoint = Math.floor(unsortedArray.length/2);
if(unsortedArray.length == 1)
{
return unsortedArray;
}
let leftArray = mergeSort(unsortedArray.slice(0,midpoint));
let r
最近我一直在学习算法设计,它涉及到在哪里获得增长的顺序(如果我错了)。我已经看到从插入排序到运行时间,这是为了计算算法,也许这是最坏的情况。问题是我不能理解如何找到n。例如:
print "Hello"
for i = 0 to n:
print i * 1
print "end of program"
所以,如果我想要计算运行时间,我应该如何得到n并计算T(n)。问题是我相信我不理解基本原理。我用谷歌搜索了一下,没有什么能让我满意,而且我也不明白。
谢谢。