Dlaczego sortowanie przez wyszukiwanie ma złożoność n^2, skoro wykonuje się (n-1)+(n-2)+(n-3)... razy?

Nawet jak będę zliczać wejścia do wewnętrznej pętli w programie to dla n=10 wychodzi 45, a nie 100 wejść do wewnętrznej pętli.
I jak zliczam na papierze to tak wychodzi 9+8+7+6+5+4+3+2+1 = 45, bo odrzuca te elementy co już posortował.

#programowanie #naukaprogramowania #informatyka
@sweet_dream99 suma ciągu arytmetycznego 1..(n-1) to (1+(n-1))*(n-1)/2 = n*(n-1)/2 - czyli rzędu O(n^2). W złożoności nie chodzi o dokładną liczbę operacji, ale o to jak ta liczba operacji rośnie wraz ze wzrostem danych wejściowych.
  • Odpowiedz
Oprócz tego co pisali wyżej, to taka uwaga:

n=10 wychodzi 45, a nie 100


@sweet_dream99: To teraz policz dla dla n=20 (dwa razy większe) i wychodzi 190 (ponad 2x2 razy więcej), więc przy dwukrotnym wzroście wielkości danych czas rośnie ponad cztery razy. Przy n=100 (10 razy więcej) wychodzi 4950 (ponad 10x10 razy więcej). To nie jest złożoność liniowa, a właśnie kwadratowa, bo zwiększenie x razy wielkości wejścia powoduje wzrost czasu wykonania
  • Odpowiedz
TIMELAPSE praca zdalna programisty! Oczekiwania kontra rzeczywistość! IT Week Timelapse z jednego dnia pracy zdalnej KOMPUTEROWCA w trakcie trwania #koronawirus Zobacz jak wyglądają oczekiwania pracy zdalnej w porównaniu z rzeczywistością ;)

Timelapse z pracy zdalnej w domu. W obecnych czasach kryzysu warto pomyśleć "czego się oczekuje", a jak wygląda rzeczywistość #pracazdalna #pracait #heheszki #itweek #naukaprogramowania
ItWeek - TIMELAPSE praca zdalna programisty! Oczekiwania kontra rzeczywistość! IT Wee...

źródło: comment_15859966629VjFHFyNngfh3P6gxcqeOz.jpg

Pobierz
Mirki co dalej polecacie? Mam 3 lata expa w javie, jest to mój jedyny język, którego dobrze znam. Jsa i c/c++ tylko z laborek na studiach. Poza tym znam frameworki typu spring/hibernate, kafka/aws/docker, trochę spring cloud, elasticsearch i zrobiłem jakiś jeden prosty projekcik z architekturą mikroserwisów. Trochę mi się nudzi więc zastanawiam się nad:
- nauka dodatkowego języka, np. python (potem machine learning), albo funkcyjny? scala?
- Google cloud?
- może react/angular?
@nick230: Poducz się podejścia funkcyjnego, strumieni, asynchroniczności. Scala, Groovy, testy spocka. Wpierw zerknij na podobne języki (kod java w groovy działa), później na inne. A nuż nie będzie ci się chciało :)
  • Odpowiedz
@asterix61: Dzięki, staram się tego trzymać :)
Do tej pory miałem styczność z java + selenium no i tu ze znalezieniem jakichkolwiek materiałów nigdy nie było żadnego problemu, przy python + selenium strasznie ciężko o coś konkretnego, a już coś o python + behave to nawet w hinduskich tutorialach rzadkość ;)
  • Odpowiedz
@dedek:
Reminiscencje Twórcy Systemów cz. 6: Programming Linux Games

Jestem wielkim fanem bardzo prostego modelu, który idealnie oddaje jak się czujemy i postępujemy w zetknięciu z jakąś nową dziedziną. Na początku nie wiemy czego nie wiemy, dlatego jesteśmy w fazie “nieświadomej niekompetencji”. Tutaj zachowujemy się różnie: czasem wydaje się, że wystarczy tylko sprawdzić tu, przestawić tam i się zrobi, proste jak drut. A czasem odwrotnie: nie wiadomo z której strony ugryźć,
dedek - @dedek: 
Reminiscencje Twórcy Systemów cz. 6: Programming Linux Games

Jes...

źródło: comment_1585897681Oh1r0h1Vif2wkOOnlrPDTY.jpg

Pobierz
@no_czesc: dzięki :) Jeszcze kilka uniwersalnych kawałków o zdobywaniu wiedzy, tworzeniu i rozwijaniu systemów zostało do opisania. Fajnie wiedzieć, że ktoś to czyta i korzysta.
  • Odpowiedz
via Wykop Mobilny (Android)
  • 1
@dedek: Sam nie wiem jak znalazłem Twoje wpisy, chyba po prostu zbieżność czasu i miejsca, jak pojawiło się w nowych wpisach, a ja akurat lurkowałem :) Masz całkiem fajne przemyślenia i spostrzeżenia, a poza tym po prostu dobrze się czyta.
  • Odpowiedz
Jak się nazywa coś takiego w javie.

Np w C# jak używam Directory.GetFiles(path, filtr,SearchOptions)
i jako 3 parametr podaje SearchOptions.AllDirectories lub SearchOptions.CostamTopDictionaries

A ja chciałbym sobie zrobić klase jakas klase Solver i dac np IterateVariables.InOrder IterateVariables.Random IterateValues.InOrder, IterateValues.Random.

#java #naukaprogramowania
Czołem Mirki i Mirabelki
Dziś nowy kurs z #bazydanych dla średniozaawanswowanych z #sql i #oracle.
W dzisiejszym wpisie kontynuuję tematykę związaną z łączeniem tabel dlatego zapraszam do kursu:
* SORT MERGE JOIN w SQL

Właściwie skończyłem część o łączeniu tabel dlatego dajcie znać jaki "cykl" rozpocząć. Dajcie znać w ankiecie lub komentarzach poniżej ( ͡° ͜ʖ ͡°)

Planuję aby kolejne kursy dotyczyły:
* Kurs SQL SQL INSERT

Kolejny cykl średniozaawansowany

  • Partycjonowanie 39.3% (11)
  • Indexy Bitmapowe 28.6% (8)
  • Statystyki 28.6% (8)
  • W komentarzu.... 3.6% (1)

Oddanych głosów: 28

Możesz użyć (wiem, staromodny będę) konstruktora:

jf.addKeyListener(new MyKeyEvent(js));
Użyłem Twojego fragmentu kodu, ale poprawiając ważną rzecz: klasy mają nazwy zaczynające się z wielkiej litery ;)
  • Odpowiedz
@dedek:
Reminiscencje Twórcy Systemów cz. 5: Koncentracja, perspektywa, zaciemnienie

Dzisiaj napiszę o dwóch kluczowych cechach najlepszych twórców systemów oraz poruszę ideę studiów wyższych.

Powszechnie spotykam się z opinią, że studia to strata czasu i w obecnych czasach można zostać wysoko opłacanym specjalistą bez wyższego wykształcenia. Nie zaprzeczę, znam kilku świetnych programistów, którzy rzucili studia we wczesnych latach i nie przeszkodziło im to w karierze. To ludzie operatywni, nie boją się rzucić
dedek - @dedek: 
Reminiscencje Twórcy Systemów cz. 5: Koncentracja, perspektywa, zac...

źródło: comment_1585815563nuGltdEMldBoaMTWf3AOpA.jpg

Pobierz
  • Odpowiedz
@dnaprawa: cgroups powstało podglądając rozwiązania zaimplementowane w OpenVZ.


@ddzwon: większość rzeczy na świecie, które człowiek wymyślił powstało na tej zasadzie: "Weżmy to co już jest i dodajmy nieco od siebie" :)
  • Odpowiedz
powstało OpenVZ, ale to właśnie OpenVZ zrobiło olbrzymią rewolucje. Teraz już zapominane i wypierane przez LXC i dockera.


@ddzwon: OpenVZ przeniosło wiele rozwiązań do mainline, kiedyś pisali że 80% kodu i stało się to bazą do rozwiązań LXC/cgroups.
  • Odpowiedz