complexity-theory

6Ciepło

2Odpowiedz

Złożoność dla maxheight funkcji w binarnym drzewie

Funkcja: MAX-HEIGHT(node) if(node == NIL) return -1; else return max(MAX-HEIGHT(node.leftChild), MAX-HEIGHT(node.rightChild)) + 1; Załóżmy, że mamy N węzłów i wywołać funkcję z

10Ciepło

2Odpowiedz

Dlaczego P ⊆ współ-NP?

Widziałem kilka miejsc, które po prostu stwierdziły, że wiadomo, że P to podzbiór przecięcia NP i współ-NP. Dowody, które pokazują, że P jest podzbiorem NP, nie są trudne do znalezienia. Aby pokazać,

6Ciepło

3Odpowiedz

Najszybszy algorytm obliczania wyznacznika macierzy?

W celu napisania pracy badawczej zlecono mi badanie najszybszego algorytmu obliczania wyznacznika macierzy. już wiem o LU dekompozycji i Bareiss algorytm który zarówno przebieg w czasie O (n^3), ale p

5Ciepło

2Odpowiedz

Złożoność w algorytmie rekursji

Obecnie studiuję struktury danych na uniwersytecie i natknąłem się na pytanie o złożoność rekursji. Biorąc pod uwagę ten kod: Unsigned func (unsigned n) { if (n ==0) return 1; if(n==1) return 2;

7Ciepło

2Odpowiedz

Problemy z partycją Brute Force Algorithm

Próbuję wykonać pseudocode dla problemu partycji poniżej w bruteforce. zestaw liczb całkowitych X i liczba całkowita k (k> 1). Znajdź k podzestawów X takich , że liczby w każdym podzestawie sumują się

6Ciepło

2Odpowiedz

Jaka jest różnica między O (1) i Θ (1)?

Znam definicje obu z nich, ale z jakiego powodu czasami widzę O (1) i inne czasy Θ (1) zapisane w podręcznikach? Dzięki.

5Ciepło

1Odpowiedz

Jak obliczyć T (N) dla tego primes algorytm Finder

ten algorytm znaleźć wszystkie liczby pierwsze poniżej N var f = function(n){ var primes = [2]; //1 var flag; //1 for(var i=3; i<n; i+=2){ // (from 3 to n-1)/2 flag = true; //1

7Ciepło

3Odpowiedz

Czas Złożoność algorytmu (zagnieżdżonych pętli)

Próbuję dowiedzieć się złożoność czasową tego Pseudokod dany algorytm: sum = 0; for (i = 1; i <= n; i++) for (j = 1; j <= n/6; j++) sum = sum + 1; wiem, że pierwsza linia biegnie n razy

8Ciepło

1Odpowiedz

Znajdź czy każda postać w 1 ciąg jest istnieć w innym ciągiem, szybciej niż O (n^2)

Biorąc pod uwagę, że 2 ciągi: String stringA = "WHATSUP"; String stringB = "HATS"; Chcę dowiedzieć się, czy każdy znak w stringB HATS istnieje w podejściu młodszym, proces można wykonać w zagnieżdż

5Ciepło

1Odpowiedz

Obliczeniowa złożoność konwersji bazy

Jaka jest złożoność konwersji bardzo dużej liczby n-bitowej na reprezentację dziesiętną? Moja myśl jest taka, że elementarny algorytm powtarzanego podziału całkowitoliczbowego, pobierający pozostało