Byla vydána OpenIndiana 2026.10. Unixový operační systém OpenIndiana (Wikipedie) vychází z OpenSolarisu (Wikipedie).
Americký výrobce polovodičů onsemi (ON Semiconductor) zrušil plány na rozšíření výroby v rožnovském závodě v Česku za dvě miliardy dolarů (podle aktuálního kurzu zhruba 43,5 mld. Kč). Důvodem je vývoj na trhu.
O víkendu probíhá na FIT VUT v Brně konference OpenAlt 2026 o otevřeném softwaru a datech, IT bezpečnosti, DIY a IoT. Na programu je spousta zajímavých přednášek. Pokud jste v Brně, stavte se. Vstup zdarma. Přednášky lze sledovat i online na VHSky a YouTube.
Qualcomm uzavřel víceletou dohodu se SpaceX. Bude dodávat rádiové technologie, baseband jednotky a software pro plánovanou pozemní 5G síť Starlink Mobile. Výstavba má zahrnovat desítky tisíc základnových stanic v USA. Zahájení nasazování se očekává v roce 2027. Qualcomm dohodu označuje za svůj dosud největší 5G kontrakt.
Google rozšířil Cloud Vulnerability Reward Program. Nově nabízí odměnu až 250 tisíc dolarů za vysoce závažné architektonické bezpečnostní chyby označované jako Root-in-Cloud.
V březnu byla oznámena spolupráce GrapheneOS s Motorolou. Nejnovější vlajka Motorola Signature 27 je první Motorola s oficiální podporou GrapheneOS. GrapheneOS (Wikpedie) je varianta Androidu zaměřující se na bezpečnost a soukromí.
Omarchy (Wikipedie) je linuxová distribuce s dlaždicovým správcem oken Hyprland. Založena je na Arch Linuxu. Vydána byla v nové verzi 4.5.0. Nově také pro Apple Silicon, konkrétně pro M1/M2/M3/Neo MacBooky.
Byla vydána nová stabilní verze 8.3 webového prohlížeče Vivaldi (Wikipedie). Postavena je na Chromiu 156 s bezpečnostními opravami z Chromia 157. Přehled novinek i s náhledy v příspěvku na blogu.
Pak je složitost algoritmu skutečně lineární (i když jsou slova neomezené na délce)... O(L + m) kde L je součet všech délek řetězců a m je konstanta.
To je klasický příklad zavádějící formulace. Podobným způsobem byste totiž snadno došel k závěru, že každý algoritmus je (přinejhorším) lineární, pouze stačí vhodně zvolit, vůči čemu má být lineární… :-)
U třídících algoritmů se časová složitost váže k počtu tříděných elementů. V tomto případě je to L, což je součet délek vstupních řetězců.
Tak to tedy není. Nezlobte se na mne, ale počet řazených elementů je počet řazených řetězců. Neřadíte znaky, řadíte řetězce (tím spíš, že jste se minule sám zmiňoval o tom, že ve skutečnosti nebudete manipulovat se samotnými řetězci, ale pouze s pointery na ně).
Je to jen násobek dvou čísel, platí: O(n*c) = O(n)Tak především součin a ne násobek - a to souvisí s tím zamlžováním, o kterém jsem mluvil, ono totiž O(kn) je ve skutečnosti něco podstatně jiného než O(n). Prohlášením nepohodlných kritérií rozsahu problému za konstanty a vhodnou volbou parametru, vůči němuž budeme časovou složitost vyjadřovat, lze prohlásit za lineární jakýkoli algoritmus… Pokud má mít ale takové tvrzení nenulovou informační hodnotu, musí být jasně řečeno, vůči kterému parametru je to lineární, jaké základní operace považujete za konstatní v čase a které parametry rozsahu problému považujete za konstanty.
. Řekl bych, že zmatek do toho zavádíš ty. Vstupy (délky) řetězců sice vždy budou konečné, ale žádnou konstantou omezené nejsou. Přirozených čísel je taky nekonečně mnoho, ale žádné není nekonečné.
Když mluvíš o složitosti algoritmu, musíš říct vůči čemu tu složitost počítáš. Když se mluví o třídících algoritmech, tak pokud není uvedeno jinak, implicitně se myslí počet tříděných prvků (v našem případě řetězců).
n.
Tohle je ale právě princip níže odkazovanýho radix-sortu. Pro třídění řetězců různé délky pak lze využít zobecněného radix-sortu. Popis algoritmu nalezneš v: Hudec: Programovací tecniky, ČVUT 2004. Složitost algoritmu je O(n + L), kde L je součet délek všech řazených slov.
Podle toho, co tady doposud zaznělo, předpokládám, že vám jde o skupinu algoritmů, kterým se říká radixsort.
Dále se praví, že je to algoritmus s lineární složitostí, ale pouze pokud m << n (je výrazně menší než n). Jak může mít algoritmus lineární složitost jen v některých případech? Vždyť i když bude prvků abecedy třeba milion, pořád s přibývajícím n poroste čas lineárně.
Tiskni
Sdílej: