asymptotic-complexity

-1열

1답변

Edmonds-Karp 알고리즘은 소스와 싱크 t 간의 최단 거리가 일 때 최단 경로가 증가 할 때마다 단조롭게 증가한다고 말합니다. 이 가정으로 소스 s와 싱크 t 사이의 거리는 | V |보다 크지 않을 것입니다. - 1. 나는 | V | 후에 소스 S와 싱크 T 사이에 더 이상 경로가 없다는 것을 의미한다고 생각한다. - 1 증강. 이것이 사실이라면 최

0열

1답변

lgn과 log8n 사이의 점근 관계가 logn이 Θ (log8n)와 같은 이유는 무엇입니까?

나는 다음과 같은 질문에 대한 정답을 이해하려고 노력 해요 : screen shot of question 대답은 LGN은 선택의 세 가지를 모두 포함하는 log8n의 세타,라고 할 수 있기 때문에 모두 사실이었다 . n의 양수 값이 logn이 log8n보다 클 것이기 때문에 이것은 혼란 스럽습니다. 맞습니까? logn이 log8n에 의해 단단히 묶여 있다고

0열

1답변

설명과 함께 다음 코드의 시간 복잡성?

이 알고리즘의 복잡도는 얼마이며 그 이유는 무엇입니까? int count = 0; for (int i = N; i > 0; i /= 2) { for (int j = 0; j < i; j++) { count += 1; } } 정답은 O (n)이지만 O (nlogn)를 얻습니다. 아무도 왜 O (n)인지 말해 줄 수 있습니까

0열

1답변

GCD 알고리즘의 실행 시간은?

unsigned int gcd(unsigned int n, unsigned int m) { if (n == 0) return m; if (m == 0) return n; while (m! = n) { if (n > m) n = n − m; else m = m − n; } return n; } whi

0열

1답변

메모리 사용량 및 JavaScript 객체의 복잡도 순서

JavaScript 객체는 기본적으로 키/값 쌍의 모음이므로 해시 맵으로 사용하기 쉽습니다. 나는 메모리 사용과 저장 및 검색에 드는 시간 비용에 관심이있다. 나는 이것에 대한 해답이 자바 스크립트 엔진의 구현과 다르다고 생각한다. MDNWikipedia hashmap article에 대한 링크는 있지만, 해시 테이블이 개체에 얼마나 큰지는 잘 모릅니다.

0열

1답변

합산 표기법을 사용하여 알고리즘을 증명하는 방법은 Θ (log n)입니까?

한다고 가정 나는 다음과 같은 코드가 있습니다 int sum = 0; int val=128; for (int i=n; i>=1; i=i/2) { for (int j=1; j<val; j++) { sum ++; } } 방법이이 Θ 수학적으로 (로그 n) 인 것을 입증 할 것입니까? 내 일반적인 접근 방식은 합계 (시그마 표

-1열

1답변

3Sum.java의 점근 적 복잡성을 찾는 법

ThreeSum.java에서 함수 수와 printall의 시간 복잡도를 어떻게 구합니까? public static void printAll(int[] a) { int n = a.length; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { for (int

0열

1답변

은이 알고리즘의 점근 적 시간 복잡성입니다. O (log n)?

P를 찾을 psuedocode 알고리즘이다 peakreturn(H) for p=1 to m //m is the length of H if H[p-1] ≤ H[p] and H[p] ≥ H[p+1] then return p return nil // only returns this if there is no peak 하는 "P"가 피크 소자이고이

3열

2답변

Stein의 알고리즘에 대한 최악의 경우 입력은 무엇입니까?

나는 Stein 's Algorithm (binary GCD algorithm)에 대한 반복 관계를 생각해 내려고 노력하고 있지만, 그것을 추적 할 수있는 능력은 최대 스크래치가 아닌 것으로 증명됩니다. 저는 다중 경로와 재귀 호출뿐만 아니라 값 자체가 아닌 값을 표현하기위한 전체 비트를 처리한다는 사실에 완전히 난처한 상황입니다. stein(u, v):

1열

1답변

는

내가 이해 니펫 같은 간단한 문구 : int x = 5; // is 1 or O(1) 그리고 while 루프와 같은 : 하나의와 while(i<); // is n+1 or O(n) 과 동일 for 루프 (의존). 동안이나 같은 루프 중첩으로 : 또한 언제 우리가 효과를 두 배로 한 for(int i = 0; i<n; i++){ // this is n