Byla vydána nová verze 25.05.11 svobodného multiplatformního video editoru Shotcut (Wikipedie) postaveného nad multimediálním frameworkem MLT. Nejnovější Shotcut je již vedle zdrojových kódů k dispozici také ve formátech AppImage, Flatpak a Snap.
Svobodný elektronický platební systém GNU Taler (Wikipedie, cgit) byl vydán ve verzi 1.0. GNU Taler chrání soukromí plátců a zároveň zajišťuje, aby byl příjem viditelný pro úřady. S vydáním verze 1.0 byl systém spuštěn ve Švýcarsku.
Spolek OpenAlt zve příznivce otevřených řešení a přístupu na 209. brněnský sraz, který proběhne tento pátek 16. května od 18:00 ve studentském klubu U Kachničky na Fakultě informačních technologií Vysokého učení technického na adrese Božetěchova 2/1. Jelikož se Brno stalo jedním z hlavních míst, kde se vyvíjí open source knihovna OpenSSL, tentokrát se OpenAlt komunita potká s komunitou OpenSSL. V rámci srazu Anton Arapov z OpenSSL
… více »GNOME Foundation má nového výkonného ředitele. Po deseti měsících skončil dočasný výkonný ředitel Richard Littauer. Vedení nadace převzal Steven Deobald.
Byl publikován přehled vývoje renderovacího jádra webového prohlížeče Servo (Wikipedie) za uplynulé dva měsíce. Servo zvládne už i Gmail. Zakázány jsou příspěvky generované pomocí AI.
Raspberry Pi Connect, tj. oficiální služba Raspberry Pi pro vzdálený přístup k jednodeskovým počítačům Raspberry Pi z webového prohlížeče, byla vydána v nové verzi 2.5. Nejedná se už o beta verzi.
Google zveřejnil seznam 1272 projektů (vývojářů) od 185 organizací přijatých do letošního, již jednadvacátého, Google Summer of Code. Plánovaným vylepšením v grafických a multimediálních aplikacích se věnuje článek na Libre Arts.
Byla vydána (𝕏) dubnová aktualizace aneb nová verze 1.100 editoru zdrojových kódů Visual Studio Code (Wikipedie). Přehled novinek i s náhledy a videi v poznámkách k vydání. Ve verzi 1.100 vyjde také VSCodium, tj. komunitní sestavení Visual Studia Code bez telemetrie a licenčních podmínek Microsoftu.
Open source platforma Home Assistant (Demo, GitHub, Wikipedie) pro monitorování a řízení inteligentní domácnosti byla vydána v nové verzi 2025.5.
OpenSearch (Wikipedie) byl vydán ve verzi 3.0. Podrobnosti v poznámkách k vydání. Jedná se o fork projektů Elasticsearch a Kibana.
. . delka = 1; for (i = 0; i < n-1; i++) for (j = i+1; j < n; j++) { sym = 1; for (k = 0; i+k < j-k; k++) of (a[i+k] != a[j+k]) sym = 0; if (sym && (j-i+1 > delka)) delka = j-i+1; } . . .A to je časově poměrně dost náročný Jinak n je délka řetězce a délka je velikost onoho nejdelšího úseku... ostatní je jasný bych řekl... Díky moc za každou radu
#include <stdio.h> int main(int argc, char **argv) { char *start, *end, *lpos, *i, *j; int lhalf = 0; if (argc >=1 ) return 1; start = argv[1]; for(end = start; *end; end++); for(lpos = i = start; i < end - lhalf; i++) { for(j = i; j>=start && (i + 1 + (i - j) < end) && *j == *(i+1+(i-j)); j--); if( i-j > lhalf) { lhalf = i-j; lpos = j+1; }; }; if(lhalf) { *(lpos + 2*lhalf) = 0; printf("%s\n", lpos); return 0; } else { return 1; } }
if (argc <=1 ) return 1;
ukkonen95()
se nám n
krát volá funkce upDate()
a canonize()
. A copak to tu máme uvnitř funkce upDate()
? Na dvou místech se nám tu volá funkce test_and_split()
to jednou doknce uvnitř cyklu! Takže jen funkce test_and_split()
je volána více než O(n). No pak tu máme další volání funkce canonize()
uvnitř funkce upDate()
a zase uvnitř cyklu! Funkce canonize()
je opět volána vícě než O(n)! No a aby to nebylo málo, tak funkce canonize()
opět obsahuje cyklus z čehož vyplývá, že ta část uvnitř cyklu se provede ještě víckrát než samotná funkce canonize()
, která sama o sobě není volána O(n), ale víckrát. Takže prdlačky švagrová. Ten algoritmus není O(n) ani kdybych zavřel obě oči a praštil se palicí do hlavy. Dokonce bych ho typoval tak na O(n^3) ná základě tohoto rozboru. Když to srovnám s kódem co jsem poslal, který má nejhorší odhad (n+2)*n/8 tedy O(n^2) a to počítám opravdu ten nejhorší případ. Nesmíš taky věřit všemu co se kde píše. Ono takhle akademicky to vypadá dobře, ale když jdeš po tom algoritmu do důsledku tak se nám tam n
krát zavolá cosi co má v sobě cyklus uvnitř něhož se nám zase zavolá ?
krát cosik a to cosik má v sobě cyklus, která může být zavolán m
krát, přičemž hodnota m
je nějaká konstanta*n
. Tedy přinejmenším O(n^2), ale taky možná O(n^3) protože neznám ?
. Abych pravdu řek, nechce se mi po tom pátrat, ale vzhledem k tomu, že je to cosi se stromy, tak tomu dejme O(n^2*log2n) ať nežeru. O(n) fakt ani omylem.
ukkonen95()
jsou funkce upDate()
a canonize()
volány vždy n
krát. Uvnitř funkce upDate()
je funkce test_and_split() vždy volána nejméně jednou, ale může být i více krát. Stejně tak funkce canonize()
je vždy n
krát volána přímo z ukkonen95()
a může být volána i z upDate()
a to i více než jednou. Takže tu máme dvě funkce, které mohou být volány n*a
, kde a
není nikdy menší než 1, ale a s velkou pravděpodobností závisí na složitosti stromu tedy asi na O(log2n). No a v samotné funkci canonize()
máme cyklus, který závisí na délce subřetězce, tedy na n
. Takže tvrdit o něčem takovém, že to má složitost O(n), je prostě lež jako věž. To neukecáte, ani kdyby jste se na hlavu postavil. Jen proto, že se v javě až tak nevyznám, jsem možná přehlédl ještě nějaké to kopírování v paměti zase se složitostí O(n), které nám z toho všeho pěkně udělají nejméně O(n^2) jako když vyšije. Mužete to milionkrát okecat, ale O(n) to prostě není.
Nehodlám nic ukecávat, to, co jste předvedl, nemá s důkazem dolního odhadu časové složitosti nic společného a ...Ahá, takže ono jde o dolní odhad složitosti, tak to ten můj algoritmus má taky dolní odhad O(n). Pro řetězec neobsahující žádnou dvojici za sebou jdoucích stejných znaků se provede právě
n-1
porovnání. Aha, takže proč to dělají tak složitě? Ten můj algoritmus je mnohem jednodužší a má stejný dolní odhad složitosti Mám fakt rád tyhle akademické "počítání" složitosti.V tom pripade vam doporucuji toto PDF.
Tiskni
Sdílej: