Czy są jakieś problemy, które stają się łatwiejsze wraz ze wzrostem wielkości?

62

To może być śmieszne pytanie, ale czy można mieć problem, który staje się łatwiejszy w miarę wzrostu wielkości nakładów? Wątpię, żeby jakieś praktyczne problemy były takie, ale może uda nam się wynaleźć zdegenerowany problem, który ma tę właściwość. Na przykład być może zaczyna się „rozwiązywać”, gdy robi się większy lub zachowuje się w inny dziwny sposób.

algorithms asymptotics dsaxton
źródło

7

Jednym z prawdziwych problemów z tą właściwością, która przychodzi mi na myśl, jest niesolone łamanie haseł, gdy jest sformułowane jak „biorąc pod uwagę n haszy, złam przynajmniej jeden hasz”. Ponieważ prędkość pękania byłaby skalowana liniowo za pomocą n, czas działania byłby proporcjonalny do 1 / n - z tym wyjątkiem, że nie możemy faktycznie przypisać ostatecznego czasu, ponieważ pękanie jest stochastyczne i nie ma stałej górnej granicy czasu.

amon

1

@amon Czas działania nie jest skalowany jak . Potrzeba czasu tylko czytać mieszań już zostały podane jako wejście!

1 / n

$1/n$

n

$n$

n

$n$

David Richerby,

3

Czy masz na myśli łatwiej w kategoriach bezwzględnych lub względnych? Jakie miary kosztów są dozwolone? Czy potrzebujesz ściśle obniżających się kosztów, czy też niewystarczające (od pewnego momentu) wystarczające?

Raphael

2

@DavidRicherby W tym przykładzie uzasadnione jest zignorowanie kosztu odczytu danych wejściowych, o ile nie wypowiemy się na temat kosztów bezwzględnych. Zamiast tego prędkość wzrasta liniowo wraz z wejściem. Dlatego n • T (1)> T (n), nawet biorąc pod uwagę koszt odczytu danych wejściowych. Tj. W przypadku tego problemu łatwiej jest rozwiązać duży wkład naraz, niż podzielić go, nawet jeśli problem jest podzielny. Nie twierdzę, że T (n)> T (n + 1) dla wszystkich n.

amon

4

Do każdego, kto chce opublikować kolejną odpowiedź z formularza: „Pewien problem, w którym dane wejściowe to pytanie, oraz mnóstwo wskazówek na temat odpowiedzi”: To nie działa. Najtrudniejsze dane wejściowe o długości to te, w których używasz wszystkich bitów, aby zadać pytanie i nie dać żadnych wskazówek. Fakt, że łatwo jest poradzić sobie z krótkimi pytaniami z wieloma wskazówkami, nie oznacza, że najgorszy czas działania jest dobry.

n

$n$

n

$n$

David Richerby,

39

Nie, nie jest to możliwe: przynajmniej nie w sensie asymptotycznym, gdzie wymagasz, aby problem stawał się coraz łatwiejszy, na zawsze, jako . $n \to \infty$

Niech będzie najlepszym możliwym czasem działania dla rozwiązania takiego problemu, gdzie jest rozmiarem danych wejściowych. Zauważ, że czas działania jest liczbą instrukcji wykonanych przez algorytm, więc musi być liczbą całkowitą nieujemną. Innymi słowy, dla wszystkich . Teraz, jeśli weźmiemy pod uwagę funkcję , widzimy, że nie ma takiej funkcji, która ściśle monotonicznie spada. (Czymkolwiek jest , musi być skończone, powiedzmy ; ale ponieważ jest monotonicznie ściśle malejące, i $T(n)$ $n$ $T(n) \in \mathbb{N}$ $n$ $T: \mathbb{N} \to \mathbb{N}$ $T(0)$ $T(0)=c$ $T$ $T(c) \le 0$ $T(c+1) \le -1$ , co jest niemożliwe.) Z podobnych powodów nie ma funkcji, która asymptotycznie ściśle zmniejsza się: możemy podobnie udowodnić, że nie ma funkcji czasu działania gdzie istnieje tak że dla wszystkich , spada monotonicznie ściśle (każda taka funkcja musiałaby ostatecznie stać się negatywna). $T(n)$ $n_0$ $n \ge n_0$ $T(n)$

Tak więc taki problem nie może istnieć z tego prostego powodu, że czasy działania muszą być liczbami całkowitymi nieujemnymi.

Zauważ, że ta odpowiedź obejmuje tylko algorytmy deterministyczne (tj. Najgorszy czas działania). Nie wyklucza to możliwości zrandomizowanych algorytmów, których oczekiwany czas działania jest ściśle monotonicznie malejący, na zawsze. Nie wiem, czy taki algorytm może istnieć. Dziękuję Beni Chernivsky-Paskin za tę obserwację .

DW
źródło

9

To niezły dowód, ale nie zgadzam się z tym założeniem. Zamiast prosić o ściśle monotonicznie zmniejszające się środowisko wykonawcze, pytanie może bardziej uzasadnione wymagać funkcji, w której istnieje a, bz <b, tak że T (a)> T (b), tj. Jego nie ściśle monotonicznie malejące. Wtedy oczywiście można znaleźć odpowiednie funkcje liczb całkowitych. Ale dlaczego liczby całkowite? Miałem wrażenie, że czas działania oznacza czas, a nie liczbę instrukcji (z wyjątkiem oczywiście maszyn Turinga) i że wyrażenie T może wykorzystywać operacje niecałkowite, takie jak log () lub wykładniki niecałkowite.

amon

2

@amon ”czas działania oznacza czas, a nie liczbę instrukcji” Absolutnie nie. Czas działania jest zawsze liczbą instrukcji. Cokolwiek innego byłoby niemożliwe do uzasadnienia, ponieważ zależałoby to od niewiarygodnie wielu szczegółów implementacyjnych.

David Richerby,

3

Choć pytanie jest niejasne, nie rozumiem, w jaki sposób wyklucza funkcję kosztu, powiedzmy, . Teraz ale dla „małego” , więc problem „staje się łatwiejszy”, mówiąc relatywnie. (Oczywiście koszty bezwzględne rosną asymptotycznie).

T (n) = n^{2} \cdot (1 + ϵ)^{- n} + n

$T(n) = n^2 \cdot (1+\epsilon)^{-n} + n$

T (n) \sim n

$T(n) \sim n$

T (n) \approx n^{2}

$T(n) \approx n^2$

n

$n$

Raphael

2

@Raphael, nie stanowi problemu, staje się łatwiejszy: staje się większy, gdy staje się większy, więc problem staje się trudniejszy, gdy staje się większy, gdy jest wystarczająco duże. W pierwszym zdaniu mojej odpowiedzi stwierdziłem, że żaden problem nie może być łatwiejszy na zawsze. Oczywiście problem może się na chwilę powiedzmy, że może się zmniejszać przez ), ale nie może być łatwiej na zawsze.

T (n) \sim n

$T(n) \sim n$

T (n)

$T(n)$

n

$n$

n

$n$

n

$n$

T (n)

$T(n)$

n \leq c

$n \le c$

DW

1

T

$T$

25

Chociaż nie jest to całkiem odpowiednia odpowiedź na twoje pytanie, algorytm wyszukiwania ciągów Boyera-Moore'a jest już blisko. Jak Robert Moore na swojej stronie internetowej o algorytmie mówi:

Nasz algorytm ma szczególną właściwość, która, z grubsza mówiąc, im dłuższy jest ten wzór, tym szybciej idzie algorytm.

Innymi słowy, ogólnie mówiąc, algorytm szuka wystąpienia ciągu docelowego w ciągu źródłowym i ustalonego ciągu źródłowego, im dłuższy jest ciąg docelowy, tym szybciej działa algorytm.

Rick Decker
źródło

10

Prawdopodobnie wzorzec nie ma rozmiaru problemu, ale długość przeszukiwanego łańcucha to długość. Tak jak w powyższym komentarzu Davida Richerby'ego , argumentowałbym, że długość wzorca jest raczej wskazówką, jak rozwiązać problem (chodziło o wyszukiwanie ciągu) niż sam problem (sprawdzenie, czy wzór pasuje do ciągu o określonej długości .)

Kevin

4

\sqrt{n}

$\sqrt{n}$

n

$n$

\log n

$\log n$

10

Jest oczywiste, że z czysto matematycznego punktu widzenia, wyłącznie algorytmu CS, jest to niemożliwe. Ale w rzeczywistości istnieje kilka rzeczywistych przykładów zwiększania skali projektu, które nie są intuicyjne dla użytkowników końcowych.

Wskazówki : im dłuższe są Twoje wskazówki, tym czasem mogą być łatwiejsze. Na przykład, jeśli chcę, aby Mapy Google wskazywały mi drogę na zachód 3000 mil, mógłbym jechać na Zachodnie Wybrzeże - i otrzymywać instrukcje dotyczące jazdy po terenie. Ale gdybym chciał przejść 6000 mil na zachód, skończyłbym ze znacznie prostszymi instrukcjami: wsiąść do samolotu z Nowego Jorku do Hokkaido. Wyznaczenie trasy biegowej obejmującej ruch drogowy, drogi, pogodę itp. Jest raczej trudne algorytmicznie, ale nakazanie mi wsiadania do samolotu i wyszukiwania lotów w bazie danych jest stosunkowo znacznie prostsze. Wykres trudności ASCII w funkcji odległości:

           |     /
           |    /
Difficulty |   /                  ____-------
           |  /           ____----
           | /    ____----
            ---------------------------------
                       Distance

Renderowanie : powiedz, że chcę renderować jedną twarz i rendering 1000 twarzy; dotyczy to reklamy billboardowej, więc oba końcowe zdjęcia muszą mieć wymiary 10000 na 5000 pikseli. Realistyczne renderowanie jednej twarzy byłoby trudne - przy rozdzielczości kilku tysięcy pikseli w poprzek trzeba użyć naprawdę potężnych maszyn - ale dla tłumu 1000 twarzy każda twarz musi mieć tylko dziesięć pikseli i może być łatwo sklonowana! Prawdopodobnie mógłbym renderować 1000 twarzy na moim laptopie, ale renderowanie realistycznej twarzy o rozdzielczości 10000 pikseli zajęłoby bardzo dużo czasu i potężne maszyny. Wykres trudności ASCII w porównaniu do renderowanych obiektów, pokazujący, jak trudność renderowania n obiektów na obraz o ustalonym rozmiarze szybko spada, ale powraca powoli:

           | -    
           |- -                     _________
Difficulty |   --      ______-------            
           |     ------      
           |       
            ---------------------------------
                        Objects

Kontrola sprzętu : wiele rzeczy ze sprzętem staje się znacznie łatwiejszych. „Ruch silnika X 1 stopień” jest trudny i / lub niemożliwy, a ty musisz poradzić sobie z wszelkiego rodzaju rzeczami, z którymi nie musiałbyś się zmagać w przypadku „ruchu silnika X 322 stopni”.

Zadania krótkotrwałe: Powiedz, że chcesz, aby element X był włączony (przez bardzo krótki czas ) co sekundę. Zwiększając czas działania X, będziesz potrzebować mniej złożonego oprogramowania, a także sprzętu.

Owen Versteeg
źródło

W przykładzie „wskazówek” podaj dokładnie, jaki jest problem obliczeniowy i jaki jest jego przypadek. Wcale nie jest dla mnie jasne, że twój przykład na 6 km mil jest większą instancją lub tylko prostą częścią czegoś (np. Jeśli dam ci duży wykres połączony z grafem i jeden izolowany wierzchołek, pytając ogólnie o najkrótsze ścieżki to: „trudne”, ale prośba o najkrótszą ścieżkę od izolowanego wierzchołka do dowolnego miejsca jest trywialna). Ponownie, na przykładzie renderowania, jaki jest rzeczywisty problem obliczeniowy? W jakim przypadku mierzysz złożoność?

David Richerby,

Przykład renderowania nie wydaje się być przykładem tego samego problemu: pierwszy to renderowanie pojedynczego obrazu; drugi renderuje wiele małych obrazów, a następnie wkleja wiele kopii tych obrazów w pewnym obszarze.

David Richerby,

Myślę, że wrt podczas podróży parametrami byłaby nazwa 2 miast, a n to liczba znaków do ich zakodowania.

emory

3

Są przypadki. Są to przypadki, w których kryteria sukcesu są funkcją danych, a nie próbują znaleźć jedną odpowiedź. Na przykład procesy statystyczne, których wyniki są wyrażane w przedziałach ufności, mogą stać się łatwiejsze.

Jednym szczególnym przypadkiem, o którym myślę, są problemy, które przechodzą od zachowań dyskretnych do zachowań ciągłych, takich jak przepływy płynów. Rozwiązanie małego problemu z pewnym błędem może wymagać modelowania wszystkich interakcji dyskretnych, co może wymagać superkomputera. Ciągłe zachowania często pozwalają na uproszczenia bez uzyskiwania wyników poza powiązanym błędem.

Cort Ammon
źródło

2

Pytanie jest interesujące i PRZYDATNE, ponieważ naszą filozofią w informatyce jest rozwiązywanie problemów, im więcej czytamy, tym trudniej. Ale w rzeczywistości NAJBARDZIEJ problemów przedstawionych w typowy sposób (trudny) można łatwo przedstawić w „łatwy” sposób; nawet znając odpowiedź DW (co jest błędne, biorąc pod uwagę, że łatwość nie oznacza szybszego, oznacza „mniej powolny”; więc nie musisz znajdować czasów negatywnych, nie możesz znaleźć czasu asymptotycznego).

Sztuka znalezienia jednego polega na umieszczeniu części rozwiązania, takiej jak podpowiedzi, jako wpisu i rozważeniu wprowadzenia problemu jako stałego parametru.

Przykład: Jaka jest najdłuższa droga samochodem między Londynem a Paryżem, unikając dwukrotnego odwiedzenia francuskiego i brytyjskiego miasta i nie odwiedzenia innego kraju? biorąc pod uwagę, musisz jechać do Birmingham przed Ashford, Orleanu przed Wersalem, La Rochelle przed Limoge itp.

Oczywiste jest, że ten problem z długimi wpisami będzie łatwiejszy niż z krótkimi.

Przykład użycia: Wyobraź sobie grę zarządzaną przez maszynę, a IA komputera musi ustalić, czy musi on zbadać więcej w grze, aby znaleźć więcej wskazówek, czy też, czy teraz jest czas, aby wydedukować najlepszą decyzję do podjęcia .

Juan Manuel Dato
źródło

2

Twój przykład nie działa. Instancje, które są duże, ponieważ mają tak wiele wskazówek, że wskazówki określają liniowy porządek wierzchołków wykresu są naprawdę łatwe. Jednak przypadki, które są duże, ponieważ dają duży wykres prawie bez podpowiedzi, są tak samo trudne, jak zwykły problem ścieżki hamiltonowskiej. Zatem najgorszy czas działania dowolnego algorytmu, który rozwiązuje ten problem, będzie co najmniej tak samo zły, jak najgorszy czas działania najlepszego algorytmu dla ścieżki Hamiltona, co nie wydaje się „super łatwe”.

David Richerby,

@ David, twoja odpowiedź jest całkowicie niepoprawna: 1. Wpis nie jest wykresem: duży wykres jest PARAMETREM. Tak więc problem hamiltonowski przekształca się w stałą (bardzo dużą, ale stałą). 2. Wpis jest rozwiązaniem problemu, więc: jeśli większy, oferujesz kombinatoryczne objaśnienie podpowiedzi. Wpis jednej wskazówki daje pomoc, dwie wskazówki podwójnej, trzy wskazówki będą zbliżone do 4 podwójnych ..., ponieważ eliminujesz możliwe rozwiązania. Więc to nie był hamiltonian, jest to rozwiązanie ze specjalnego wykresu, a problemem jest CO ZROBIĆ z częściami rozwiązań.

Juan Manuel Dato

Myślę, że twój argument jest interesujący, ponieważ większe przypadki są w pewnym sensie „łatwiejsze”, ale myślę, że odpowiedź na pierwotne pytanie brzmi ostatecznie „nie”. Ponieważ wykres jest skończony, istnieje zatem tylko wiele możliwych wskazówek. Dlatego każde wystąpienie można rozwiązać w stałym czasie (na przykład przy użyciu tabeli odnośników). Mimo że większe instancje są (intuicyjnie) łatwiejsze w (asymptotycznej) informatyce, wszystkie instancje są równie trudne (możliwe do rozwiązania w stałym czasie).

Tom van der Zanden

@Tom, zgadzam się, że twoje rozważania na temat złożoności będą stałe, ale problemem jest to, w jaki sposób akceptujemy nowe wskazówki: jeśli nasza filozofia obliczania długiego wpisu nie jest lepsza niż krótki zapis, musimy zmienić naszą filozofię - ponieważ to jest fakt: długie wpisy oznaczają łatwiejsze problemy. Więc nie możemy w ten sposób pracować ... Poleciłbym moją książkę, ale nie mam reputacji ...

Juan Manuel Dato

n \log n

$n\log n$

1

Rozważ program, który pobiera jako dane wejściowe to, co wiesz o haśle, a następnie próbuje je złamać. Myślę, że robi to, co chcesz. Na przykład:

Brak danych wejściowych-> Brutalna siła łamie wszystkie symbole i słowo dowolnej długości
Długość hasła -> Brutalna siła wszystkich symboli w słowie o tej długości
Zawarte symbole -> Zmniejsza listę symboli do sprawdzenia
...
Zawarte symbole, w tym wiele wystąpień i długość -> Oblicz tylko permutacje
Wszystkie symbole we właściwej kolejności -> w zasadzie rozwiązały się same

Powinienem dodać, że jest to sztuczka, ponieważ taki problem jest odwrotny do wielkości wejściowej. Możesz pominąć jedną warstwę abstrakcji i powiedzieć, że rozmiar wejściowy jest duży dla braku danych wejściowych (sprawdź wszystkie symbole i długości słów) i mały, jeśli podasz prawidłowe hasło na początku.

Wszystko sprowadza się do tego, na ile pozwalasz na abstrakcję.

RunOrVeith
źródło

2

b

$b$

0

W rzeczywistości mam problem, który zmniejsza się wraz ze wzrostem danych. Jedna z moich aplikacji rejestruje atrybuty określonego produktu, na przykład ser. Atrybutami są na przykład CheeseType, marka, kraj, obszar, MilkType itp. Co miesiąc otrzymuję listę nowych serów, które pojawiły się na rynku w tym czasie, wraz z ich atrybutami. Teraz te atrybuty są wpisywane ręcznie przez grupę ludzi. Niektóre tworzą literówki lub po prostu nie znają wartości wszystkich atrybutów.

Podczas wyszukiwania w mojej bazie danych staram się przewidzieć na podstawie statystyk, jak smakuje ser, na podstawie tych atrybutów. Co się dzieje, to że dla każdego atrybutu otrzymuję zakres wartości; niektóre są ważne niektóre są nieprawidłowe. Wyeliminowanie lub poprawienie tych nieprawidłowych jest możliwe tylko wtedy, gdy mam wystarczającą ilość danych. Chodzi o różnicę między wartościami rzeczywistymi a hałasem, bez eliminowania rzadkich, ale ważnych wartości.

Jak możesz sobie wyobrazić, przy niskim poziomie głośności hałas jest zbyt ważny, aby wszystko naprawić. Jeśli masz 5 wystąpień Cheddar, 1 Brie, 1 Bri i 1 Chedar, jak mam powiedzieć, która jest poprawna, a która literówka? Przy większej głośności literówki mają tendencję do utrzymywania się na bardzo niskim poziomie, ale rzadkie wartości otrzymują kilka kluczowych przyrostów, co pozwala im uciec od hałasu (poparte doświadczeniem). W tym przypadku mogłem sobie wyobrazić na przykład 50000 Cheddar, 3000 Brie, 5 Bri, 15 Chedar.

Więc tak, niektóre problemy rozwiązują się ostatecznie, gdy masz wystarczającą ilość danych.

Chris
źródło

1

Nie udaje się to ze zwykłego powodu. Duży wkład może być taki, w którym ludzie opowiadają o wielu różnych rodzajach sera, a nie taki, w którym opowiadają o kilku rodzajach sera, ale niektóre z nich źle je przeliterowały. Nie jest też jasne, czy „łatwiej” należy interpretować jako „pozwala na większą pewność wyniku”.

David Richerby,

Jest to prawdziwy problem (miałem go już dwa razy), którego nie da się rozwiązać przy małej ilości danych. Może, a nawet łatwiej odróżnić dobre wartości od niewłaściwych, ponieważ głośność staje się wysoka. Ma tę zaletę, że odpowiada na pytanie „Czy są jakieś problemy, które stają się łatwiejsze w miarę, jak się powiększają?” Nie ma znaczenia, ile rodzajów serów się pojawi, w końcu, przy wystarczającej objętości, będą miały więcej „hitów” niż literówki. Jest to cs .stackexchange, a nie matematyka, więc problemy są różne, a ich rozwiązanie czasami polega po prostu na większym zaufaniu do wyników.

Chris

Czy to też nie jest przesłanie programu telewizyjnego Numbers ? A przynajmniej niektóre epizody - wiem, że w szczególności pamiętam jedną scenę, w której facet matematyki zauważa, że algorytm, którego używa do rozwiązania problemu, staje się skuteczniejszy z większym zestawem danych.

Dan Henderson

2

„Staje się bardziej efektywny”! = „Staje się łatwiejszy”.

David Richerby,

-1

Rozważ problem NP-zupełny 3-SAT. Jeśli problem będzie się powiększał, wprowadzając dane wejściowe w postaci x_i = true / false, albo przerwiesz poszczególne rozróżnienia na klauzule dwóch zmiennych, tworząc w ten sposób problem 2-SAT, który jest zdecydowanie P, lub po prostu otrzymujesz odpowiedź prawda / fałsz.

W przypadku, gdy istnieje nadmiarowość w wejściach x_i = prawda / fałsz (to samo wejście pod warunkiem wiele razy lub sprzeczne dane wejściowe), możesz łatwo posortować dane wejściowe i albo zignorować nadmiarowe wartości, albo zgłosić błąd, jeśli wartości są sprzeczne.

W każdym razie myślę, że stanowi to „realistyczny” problem, który łatwiej jest rozwiązać, gdy rośnie liczba danych wejściowych. „Łatwiejszym” aspektem jest konwersja problemu NP-zupełnego na problem P. Nadal możesz grać w system, dostarczając absurdalne dane wejściowe, tak że samo sortowanie zajęłoby więcej niż brutalne wymuszenie problemu.

Teraz naprawdę fajny scenariusz byłby, gdybyśmy byli gotowi zaakceptować T (0) (wykorzystując zapis DW w powyższej odpowiedzi) może być nieskończony. Na przykład T (0) może być równoważne rozwiązaniu problemu zatrzymania Turinga. Gdybyśmy mogli wymyślić taki problem, że dodanie większej ilości danych wejściowych przekształci go w rozwiązywalny problem, uderzyliśmy w złoto. Zauważ, że nie wystarczy asymptotycznie przekonwertować go na rozwiązywalny problem - ponieważ jest to tak samo złe jak brutalne zmuszanie problemu.

v vv cvvcv
źródło

1

Te konkretne dane wejściowe stają się łatwiejsze. Jeśli jednak weźmiesz pod uwagę wszystkie możliwe dane wejściowe, 3SAT ogólnie staje się znacznie trudniejszy, gdy dodajesz więcej klauzul: twarde dane wejściowe są tymi bez tych klauzul „podpowiedzi”. Jeśli nie zezwalasz na ogólne dane wejściowe, musisz dokładnie określić, które dane wejściowe są dozwolone.

David Richerby,

Po pierwsze: zgadzamy się, że dodanie większej liczby danych wejściowych może wydłużyć czas działania. Mówię zasadniczo to samo powyżej. Po drugie, wyraźnie mówię, że bierzemy istniejący 3-SAT i dodajemy tylko dane wejściowe w postaci x_i = true / false. Myślę, że jest to wystarczająco jasne i nie muszę udzielać dalszych wyjaśnień. Myślę, że starasz się sformułować najbardziej błędną interpretację tego, co napisałem. Proszę, nie kłopocz się sobą.

v vv cvvcv

1

Niepoważnie. Jaki problem obliczeniowy rozwiązujesz? Problemem obliczeniowym jest decyzja o członkostwie w zestawie ciągów (powiedzmy, że jest to zestaw formuł, aby uniknąć kłopotów z kodowaniem). Jaki jest zestaw formuł, dla których twierdzisz, że decyzja, czy długa formuła jest w zestawie, jest łatwiejsza niż decyzja, że krótka formuła jest w zestawie? Jak tylko spróbujesz to sprecyzować, jestem prawie pewien, że twoje roszczenie rozpadnie się.

David Richerby,

Czy możesz wyrazić swoje zrozumienie „mojego roszczenia”? Jak tylko spróbujesz to sprecyzować, jestem prawie pewien, że przestaniesz marnować przepustowość Internetu.

v vv cvvcv

Jestem informatykiem, a nie czytającym w myślach. Doprecyzowanie roszczenia to praca, a nie moja.

David Richerby

-1

Pytanie brzmi: „czy można mieć problem, który staje się łatwiejszy w miarę wzrostu wielkości nakładów?” Co jeśli dane wejściowe są zasobami do wykorzystania przez algorytm do pracy nad zadaniem. Powszechnie wiadomo, że im więcej zasobów, tym lepiej. Poniżej znajduje się przykład, w którym im więcej pracowników, tym lepiej.

$n$
$t$ $p$

$n$

3) Dane wyjściowe:
Dane wyjściowe to ścieżki między zadaniami, które mają podjąć pracownicy. Każda ścieżka jest powiązana z liczbą pracowników biorących ją. Na przykład:

$n1$
$n2$
$n3$
$n4$
$n5$

4) Możliwe rozwiązanie:
Jednym z możliwych rozwiązań jest najpierw obliczenie najkrótszej ścieżki do najbliższych węzłów z A. To będzie ścieżka do przodu. Następnie rekurencyjnie oblicz ścieżkę przekazywania dla każdego odwiedzanego zadania. Rezultatem jest drzewo. Na przykład:

          ZA
      pne
    DE

$n$ $n1$ $n2$ $n2 \neq 0$

$n=\infty$ $n = 1$

$n$

yemelitc
źródło

6

Dziękuję ci, że wyraziłeś swoje zdanie. Zwykle w informatyce rozumie się, że algorytm przyjmuje sekwencję bitów jako dane wejściowe i generuje kolejną sekwencję bitów. Przy takim standardowym zrozumieniu nie rozumiem, w jaki sposób ta odpowiedź może mieć sens. Jeśli masz na myśli inne pojęcie algorytmu, myślę, że lepiej by było, gdybyś zredagował pytanie, aby opisać, co rozumiesz przez algorytm (ponieważ brzmi to tak, jakbyś nie używał tego terminu w sposób, który odpowiada standardowemu użyciu termin, jak rozumiem).

DW

Dane wejściowe mogą być po prostu liczbą (liczbą zasobów). Wpłynie to na liczbę dodatkowych obliczeń, przez które będzie musiał przejść algorytm. Przeredaguję odpowiedź, aby podać bardziej konkretny przykład.

yemelitc

Dzięki za edycję - dzięki temu jest o wiele jaśniej. Widzę teraz, że nie mylisz kosztu obliczenia rozwiązania z kosztem wykonania tego, jak pierwotnie myślałem. Ale teraz jesteśmy w zwykłej sytuacji. Po pierwsze, odczyt danych wejściowych zajmuje co najmniej czas liniowy. Po drugie, trudne przypadki to nie te, w których dajesz małe drzewo i gazillion ludzi, ale gdzie dajesz duże drzewo i stosunkowo niewiele osób. (Na przykład, jeśli pozwolisz mi na milion bitów, wybiorę drzewo z około tysiącem wierzchołków i dam ci pięć osób, a nie drzewo z pięcioma wierzchołkami i tysiącem ludzi.)

David Richerby

Zgadzam się. Wygląda na to, że wszyscy skończyliśmy dość krytycznie, w przeciwieństwie do tego, co skłoniło nas pierwotne pytanie! Ale mam nadzieję, że masz mój pomysł na „wkład jako zasób”: bez względu na to, jak duża jest praca, im więcej ludzi, tym lepiej. Nadal w asymptotycznym sensie masz zdecydowanie rację, powinienem winić to za nieujemne liczby całkowite.

yemelitc

Czy są jakieś problemy, które stają się łatwiejsze wraz ze wzrostem wielkości?

Odpowiedzi: