Wszystko

Najnowsze

Archiwum

Adaslaw
  • 2
Jak ktoś lubi rozgrzewki z #algorytmika / #algorytmy to może się rozgrzać na zadaniu:

Mamy tablicę z n liczbami naturalnymi, np.: [1, 2, 3, 5, 6, 8, 11, 1].
Mamy też liczbę k > 0.

Napisz algorytm, który przesunie elementy w tablicy (w prawo lub w lewo - tu nie jest to istotne), o k pozycji.
  • 18
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
tomekb1999
  • 1
@null_ptr: bo takie przesunięcie elementów to permutacja, a te można reprezentować jako macierze. Ja kombinowałem jeszcze z rozkładem permutacji na transpozycje, wtedy naraz zamieniamy tylko dwa elementy, to chyba też da złożoność czasową O(n).
  • Odpowiedz
AnonimoweMirkoWyznania
  • 5
#anonimowemirkowyznania
rynek juniorów w ostatnich latach to tragedia i naprawdę ciężko o jakkolwiek kompetentną osobę, ostatnio przydzielono mi rolę rekrutera technicznego w celu zatrudniania nowych juniorów i stażystów oraz weryfikowania ich wiedzy z zakresu programowania.

Jednym słowem koszmar. Polskie szkolnictwo nie działa a studenci pomimo bardzo ostentacyjnych projektów umieszczonych na Githubie nie byli w stanie napisać prostego kopca w wybranym języku programowania, mało tego nie potrafili nawet zaimplementować szukania binarnego.

Pomyślałem że
  • 17
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
z.....u
z.....u
  • 41
@AnonimoweMirkoWyznania: Bo kazesz im robic rzeczy, do ktorych znajdziesz w necie z milion roznych implementacji i kazda bedzie pewnie lepsza od ich wlasnej. Nie bronie ich, ale dzisiaj to raczej liczy sie to, zeby potrafic znalezc informacje i rozwiazac problem takimi metodami, zeby bylo szybko, tanio i skutecznie. I na tym sie skupiaja ludzie.
  • Odpowiedz
wytrzzeszcz
  • 5
#programowanie #naukaprogramowania #algorytmika
Zadanie wybierz k największych elementów z pośród n. gdzie n>>k
na chama to będzie dane.sort().head(10) ale złożoność nlogn +k bo sortowanie nie da się szybciej
tak pomyślałem że można by zaalokować drzewo na k elementów i mieć zawsze "pod ręką" wartości max/min w drzewie by wiedzieć czy jest sens wykonywać drogie wstawianie. przy jednorazowym przelocie przez zbiór
no i wyszła mi złożoność nlogk.
  • 10
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
m.....r
m.....r
  • 1
@erwit:
Notacja Θ
Mówimy, że T(n) = Θ (f(n)) jeśli istnieją stałe dodatnie c1, c2 i n0 takie n0 ∈ N, iż dla
każdego n ≥ n0 prawdziwa jest nierówność:
c1·f(n) ≤ T(n) ≤ c2·f(n)
  • Odpowiedz
Dewid
Dewid
  • 2
Mireczki potrzebuje ogarnąć temat z drzew ( B - drzewo, AVL drzewo ) oraz z list i tutaj rodzi się moja prośba.
Poratowałby ktoś linkiem, w którym jest to w miare przystępny sposób opisane?
Tak wiem, google nie gryzie, ale wole od kogoś jakieś sprawdzone źródło ( ͡° ͜ʖ ͡°) coby potem problemów nie było.

#programowanie #naukaprogramowania #algorytmy #algorytmika
  • 4
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
N.....w
N.....w
  • 2
Tak się zastanawiam jakie macie przemyślenia na temat znajomości formalnych dowodów i umiejętności ich rozwiązywania w algorytmice (ot, na przykład dowód relaksacji dla ścieżek - kojarzycie, umielibyście rozwiązać z marszu)? Wolicie stworzyć rozwiązanie i jeśli nie działa, to pomyśleć dlaczego? Jakie macie podejście do tego typu rzeczy i czy nie przeszkadza wam to w obecnej pracy? Nie macie ze sobą problemu, że jesteście gorsi w zagadnieniach matematycznych (nie tyczy się to studentów
  • 5
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
aleqsio
  • 3
Myslałes żeby przy szyfrowaniu stworzyć x wersji pliku każdy zaszyfrowany innym kluczem. Wtedy na etapie szyfrowania wstawiasz identyfikator. Jedyny problem to rozmiar pliku który jest tyle razy wiekszy, ile masz różnych kluczy.
Tak czy inaczej ciężko jest zrobić zaszyfrowany plik który można odszyfrować wieloma kluczami.
  • Odpowiedz
aleqsio
  • 1
Korzystasz wtedy z bezpiecznego, standardowego algorytmu, możesz bezpiecznie ukryć identyfikator na etapie szyfrowania. Ewentualnie podziel plik na dwie części, jedna o stałym niedużym rozmiarze do którego wstawiasz identyfikator, a druga zawierająca resztę danych. Tworzysz x części pierwszych dla każdego klucza, a drugą cześć masz jedną.
  • Odpowiedz
mk321
  • 2
#algorytmika #heheszki

Mój algorytm rozwiązujący pewien problem na moim komputerze, dla 23 danych będzie liczył go w 61423370 lat.

  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
mk321
  • 2
#programowanie #algorytmika

Problem komiwojażera (ang. travelling salesman problem, TSP).
Dla zwykłego algorytmu brute-force złożoność obliczeniowa to: O(n!).

Ale to jest dla symetrycznego (STSP) czy asymetrycznego (ATSP)? Załóżmy, że O(n!) jest dla symetrycznego. To jeśli w asymetrycznym jest dwa razy tyle do policzenia, to złożoność obliczeniowa asymetrycznego to będzie (O(2*n!)?
  • 6
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
tell_me_more
  • 1
@mk321: nom. Dla odpowiednio dużego n zawsze algorytm n! będzie wolniejszy niż algorytm n^2, nieważne, jakie stałe stoją obok.

Jeśli Ci to na studia potrzebne to jeszcze ogarnij dokładny zapis, bo tak naprawdę to tam jest kilka oznaczeń - mała omega, duża omega, mała theta i duża theta i znaczą coś trochę innego. W praktyce używa się O(..n..) i tyle, ale na studiach trza być precyzyjnym.
  • Odpowiedz
siemanko
  • 1
Witajcie. Mam problem, który pierwotnie wydawał się trywialny, ale nie mogę sobie z nim poradzić.
Otóż pracuję nad aplikacją, w której wykupuje się czas jej działania. Problemem jest wyliczenie pozostałych dni.
Dostępną mam listę płatności. Każda płatność ma informację kiedy została dokonana i ile wykupiono dni. Na podstawie tego chciałbym otrzymać liczbę dni dostępnych "na koncie". Płatności mogą się pokrywać, np. tego samego dnia można wykupić 30 dni i 60 dni.
Pierwsze
  • 10
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
pkh
  • 2
@Szab: Wydaje mi sie ze nie. Majac drzewo zrownowazone masz zapewnione ze proces dodawania i wyszukiwania jest w czasie logn. Zakladajac ze kazdy node trzyma sume swoich dzieci + swoja wartosc. To znalezienie i-node to jest operacja koszt to logn (znalezienie noda o pozycji x i zwrocenie jest wartosci plus sumy prawego dziecka - masz wtedy sume od i do roota). Potem szukasz j-node. Majac go (koszt logn) zwracasz wartosc
  • Odpowiedz

Powiązane tagi