Czy big-O naprawdę jest tak istotny podczas pracy w przemyśle?

65

W każdym wywiadzie, w którym uczestniczyłem, byłem pytany o matematyczną analizę złożoności, w tym notację big-O.

Jak istotna jest analiza Big-O dla rozwoju przemysłu? Jak często tak naprawdę go używasz i jak konieczne jest wyostrzone podejście do problemu?

durron597
źródło
5
@ MM01 Studiowałem to w szkole średniej i na uniwersytecie. Chociaż uznaję to za element wiedzy programisty, nigdy nie korzystałem z niej w żadnej pracy.
systempuntoout
27
Co dokładny przemysł jesteś kontemplując gdy pytaniem to? Czy piszesz kod kontrolny dla łazika księżycowego, czy platformy blogowej?
Tim Post
14
@systempuntoout, nigdy nie wybrałeś algorytmu, który byłby szybszy niż inny, ponieważ był szybszy?
3
@ MM01 - Jeśli masz z tym problem, jedno z najłatwiejszych (choć uproszczonych) wyjaśnień można znaleźć tutaj: rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation
Tim Post
6
@Systempuntoout, rozumienie i stosowanie notacji O nie oznacza sztywnego matematycznego dowodu, ale może w prosty sposób przekazać, jak zachowuje się twój algorytm. Jeśli potrzebujesz sortować według 1D, potrzebujesz algorytmu O (n log n). Jeśli chcesz implementacji liczby Fibbonacciego, wybierz tę, która działa w O (n). Nawet jeśli nie wypowiesz tego wprost na głos, jest to nadal skondensowana wersja liczby pętli i rekurencji, która jest niezwykle użyteczna. Oszczędza wiele słów. (A dla nitpicky - tak, k jest również ważne, jeśli jest znacznie duże lub małe).

Odpowiedzi:

76

Moje pytanie brzmi: jak istotny jest ten test dla rozwoju w branży?

Dobre zrozumienie teorii złożoności obliczeniowej (np. Duża notacja O) jest niezbędne do projektowania skalowalnych algorytmów, aplikacji i systemów. Ponieważ skalowalność ma duże znaczenie dla komputerów w przemyśle, również duża notacja O.

Jak często korzystasz z niego i jak konieczne jest wyostrzone podejście do problemu?

Zależy, co rozumiesz przez „reeeally use it”. Z jednej strony nigdy nie robię formalnych dowodów złożoności obliczeniowej oprogramowania, które piszę. Z drugiej strony przez większość dni mam do czynienia z aplikacjami, w których skalowalność jest potencjalnym problemem, a decyzje projektowe obejmują wybór (na przykład) odpowiednich typów kolekcji na podstawie ich cech złożoności.

(Nie wiem, czy możliwe jest konsekwentne wdrażanie skalowalnych systemów bez solidnego zrozumienia teorii złożoności. Byłbym skłonny myśleć, że tak nie jest.)

Stephen C.
źródło
+1, ponieważ zasady są ważne. Z mojego doświadczenia w branży wynika, że ​​należy brać pod uwagę to, że nie warto się nad tym zastanawiać. To powiedziawszy - jeśli zostaniesz zapytany o porównanie (przykładowego) wstawienia listy vs wstawienia tablicy lub sortowania bąbelkowego vs Quicksort, wówczas ankieter stara się wykorzystać twoją wiedzę. I doceń, jeśli nawet pomyślisz o złożoności / czasie wykonywania / skalowalności / wydajności. Jeśli nie będziesz / nie mógł pomyśleć o tych rzeczach, będzie kilka prac, których nie będziesz wiedział, jak robić dobrze. Rzadko, ale pojawia się od czasu do czasu.
szybko_now
6
Cóż, jest to możliwe, podobnie jak strzelanie do celów w ciemnej czerni. Biorąc pod uwagę wystarczającą liczbę kul, w końcu trafisz w dziesiątkę. Następnie, doświadczając rezultatów różnych projektów i wdrożeń, bierze się pod uwagę, co skutkuje mniejszą liczbą pocisków potrzebnych następnym razem. Zła analogia, prawdopodobnie, ale to dokładnie opisuje sposób niektóre oprogramowanie jest napisane. Podniosłem głos twojej odpowiedzi.
Tim Post
Ale zauważ również, że na „realnie” wydajność częściej wpływają problemy, które nie mają nic wspólnego ze złożonością, ale z czarnymi skrzynkami poza twoją kontrolą. Model mentalny tych pudeł jest konieczny do optymalizacji czegokolwiek. Te rozważania prawdopodobnie stają się nieważne, gdy N zbliża się do nieskończoności, co nigdy tak naprawdę nie jest.
Dr Belisarius,
@Tim Post - Powiedziałem „… konsekwentnie wdrażaj skalowalne systemy…”. Pewnie, że możesz mieć szczęście, ale nie możesz mieć szczęścia konsekwentnie. Ale jestem również gotów zaakceptować fakt, że naprawdę mądra / doświadczona osoba może rozwinąć intuicyjne zrozumienie złożoności bez zbliżania się do podręcznika lub kursu informatyki.
Stephen C
Na marginesie, doprowadziło to do dobrego śmiechu w pracy, gdy mężczyzna współpracownik powiedział kobiecej współpracownikowi, „Brzmi jakbyś miał duży problem O”, nie zdając sobie sprawy z drugiego znaczenia tego terminu. Przyjęła to w duchu, jaki miał na myśli, ale nie mogła przestać chichotać.
Paul
36

Powodem tego jest to, że wskazuje na skalowalność .

Proces, który jest O (n ^ 2), będzie skalowany gorzej niż ten, który jest O (n log n), ale lepszy niż jeden w O (n ^ 3) lub nawet O (n!).

Jeśli nie znasz różnic i kiedy mają one zastosowanie, jesteś mniej odpowiedni do wyboru odpowiednich implementacji funkcjonalności, a także do ekstrapolacji wydajności testu na wydajność produkcyjną.


EDYCJA: Porównanie 48n z n ^ 3 z http://www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (który z kolei pochodzi z Programming Pearls)

wprowadź opis zdjęcia tutaj

1249
źródło
8
+1: Najgorszym sposobem, aby dowiedzieć się, że proces nie jest skalowany, jest pojawienie się grupy krzyczących klientów naraz.
Larry Coleman
22
@ Larry, przynajmniej krzyki skalują się liniowo wraz z liczbą klientów!
10
Wydaje mi się, że to pokazuje, jak ważne jest duże-O: dźwięk jest w rzeczywistości O(log Customers)dB.
MSalters
4
@MSalters, ok, poprawiłem się: „ LICZBA krzyków skaluje się liniowo z liczbą klientów”. Poziom dźwięku to inna sprawa.
1
@ Thorbjørn Ravn Andersen: Przeczytałem kilka badań, które sugerują, że jest to bardziej logarytmiczna skala, dlatego niektóre klasy skarg klientów są tak ważne! Wskazują one, że im większa baza klientów, wiele więcej osób ma ten problem, i po prostu nie mówią nic albo idą do konkurencji.
Steven Evers
32

To zależy od tego, co robisz.

Dla twórców stron internetowych (takich jak ja) zwykle ma to duże znaczenie. Chcesz, aby aplikacje internetowe były skalowane. Jeśli Twoja aplikacja ma wąskie gardło, które skaluje się z O (n ^ 2), i uważasz, że to jest w porządku, ponieważ Twój serwer może obsłużyć 1000 jednoczesnych użytkowników, wydaje się, że nie musisz się tym przejmować. Chodzi o to, że aby obsłużyć tylko dwa razy więcej (co jest prawdopodobne, że stanie się to tuż po nocy), będziesz potrzebować 4 razy więcej mocy obliczeniowej. Idealnie byłoby, gdyby aplikacje internetowe były skalowane w O (n), ponieważ sprzęt jest tani przy rozsądnym stałym stosunku użytkownik / serwer.

Ogólnie w aplikacjach, w których masz 100 000 obiektów, duże O przyjdzie i zje ciebie. Jesteś niezwykle podatny na szczyty. Na przykład obecnie pracuję nad grą 3D, która jest aplikacją, która obsługuje mnóstwo danych. Oprócz renderowania masz kontrolę kolizji, nawigację itp. Nie możesz sobie pozwolić na oczywistą drogę. Potrzebujesz wydajnych algorytmów, potrzebujesz dużo buforowania, więc te mniej wydajne amortyzują się. I tak dalej.

Oczywiście, jeśli robisz coś w stylu tworzenia aplikacji mobilnej, łącząc GUI w projektancie interfejsu, połącz to z niektórymi usługami internetowymi i to wszystko, nigdy nie będziesz mieć problemów ze złożonością. Ponieważ usługi internetowe, do których dzwonisz, już się tym zajmują.

back2dos
źródło
Stworzenie aplikacji mobilnej to nie tylko zebranie GUI, ale wybaczę ci to wyrażenie w 2010 roku :) Architektura jest złożona, wątkowanie, przechowywanie danych, kolejki sieciowe, na urządzeniach mobilnych. Ale surowe Big O nie ma znaczenia (przynajmniej w iOS), ponieważ powinieneś używać natywnych struktur danych i algorytmów.
PostCodeism,
21

W życiu zawodowym nigdy tak naprawdę nie stosowałem formalnie tej reguły.

Musisz jednak znać tę koncepcję i stosować ją w intuicyjny sposób za każdym razem, gdy projektujesz algorytm.

Zasada jest następująca:

Powinieneś być na tyle zaznajomiony z notacją O, aby móc określić dla danego zadania, czy jest to wymagane do formalnego obliczenia, czy wystarczy intuicyjnie ją ocenić, czy też możesz ją całkowicie pominąć. Podobnie jak wiele innych podstawowych pojęć matematycznych.

Lorenzo
źródło
10

Cóż, może krótka historia wyjaśni ci, dlaczego NA PEWNO jest to konieczne:

W projekcie, nad którym pracowałem, był program odpowiedzialny za drukowanie wszelkiego rodzaju dokumentów (etykiet, list kompletacyjnych itp.) Program ten składał się z dwóch części, jednej odczytywającej wszystkie niezbędne dane z bazy danych i zapisującej je w Plik w stylu .ini oraz inna część, która odczytuje te pliki i wypełnia je w szablonach. Działa to dość dobrze w przypadku etykiet i małych list (z tylko kilkoma polami), ale działało przez prawie 10 minut, kiedy trzeba było wydrukować „dużą” listę ~ 20 stron. Ponieważ dostęp do tych plików ini spowodował czasy dostępu O (n²), gdzie n jest liczbą pól do wydrukowania.

Gdyby pierwotni programiści tego programu zrozumieli notację O, nigdy by tego nie zrobili. Zastąpienie tej głupoty haszyszem sprawiło, że była o wiele szybsza.

użytkownik 281377
źródło
8

Wydajność Big-O jest ważna, ale została w dużej mierze zinternalizowana.

Wydajność sortowania i wyszukiwania według Big-O nie ma znaczenia, ponieważ ludzie zazwyczaj korzystają z dostarczonych przez system, a te będą tak dobre, jak tylko mogą być (biorąc pod uwagę, że muszą być ogólnie przydatne). Istnieją struktury danych, które są bardziej wydajne dla różnych rzeczy, ale zwykle można je wybierać na ogólnych zasadach (i zwykle są one wbudowane w nowoczesne języki). Istnieje pewne wyczucie algorytmów, które skalują się lub nie skalują.

W rezultacie kwestie formalne rzadko pojawiają się w praktyce, ale praktyka opiera się na tych samych zasadach.

David Thornley
źródło
Naprawdę zauważasz to, gdy patrzysz na kod napisany przez kogoś, kto nie zinternalizował Big-O i jest zaskoczony, że jego podsystem działa tak okropnie w produkcji. Nawet podstawowe zrozumienie wystarczy, byś zakwestionował cztery zagnieżdżone pętle foreach na tych samych dwóch ogromnych tablicach ...
eswald
6

IMHO wiele programów informatycznych pozostawia wielu studentów wędrujących tam wśród chwastów. Programy te nigdy nie przedstawiają pełnego obrazu nauki o obliczeniach. Studenci wchodzą w branżę, zmagając się ze sposobem zastosowania koncepcji, których się nauczyli, z niewielkim wglądem w ich relacje ze światem rzeczywistym.

Powiedziałbym, że sednem nauki o obliczeniach jest umiejętność rozumowania o obliczeniach. Nauczysz się różnych metod i technik, aby to zrobić, i zastosujesz je do abstrakcyjnych problemów, które są prototypowymi prymitywami występującymi w wielu rzeczywistych problemach. Sztuką jest dostrzeżenie tych prototypowych prymitywów w prawdziwym świecie, a następnie rozumowanie takich rzeczy, jak poprawność, złożoność, czas itp., Które, możesz się zgodzić, są prawdziwymi problemami, o które musisz się martwić. Wgląd w zachowanie części często daje wgląd w zachowanie całości. I te same ogólne metody i techniki można również zastosować do całości, ale nie z taką samą rygorystycznością, jaką zapewniają mniejsze, dobrze abstrakcyjne, dobrze określone części. Ale w końcu nauka obliczeń obdarza cię zdolnością do racjonalnego myślenia decyzje o tym, jak zorganizować obliczenia, z prawdziwym wglądem w to, jak będzie się zachowywać w różnych warunkach.

Ziffusion
źródło
5

Notatka do siebie !:

Ja i wielu innych zadajemy sobie to pytanie regularnie.

Myślę, że prawdziwym powodem, dla którego o to pytamy, jest to, że jesteśmy leniwi.

Ta wiedza nigdy się nie stanie i nie stanie się przestarzała. Nie możesz stosować go bezpośrednio na co dzień, ale będziesz go używał podświadomie i będzie to miało pozytywny wpływ na twoje decyzje projektowe. Pewnego dnia może to zaoszczędzić Ciebie lub inne godziny i dni kodowania.

Ponieważ coraz więcej problemów jest zamykanych przez biblioteki i narzędzia innych firm i są dostępne dla coraz większej liczby programistów, musisz znać tę wiedzę, aby odróżnić się od innych i pomóc w rozwiązywaniu nowych problemów.

Conor
źródło
5

Nie całkiem. Zasadniczo jedyny raz, kiedy o tym myślę, to dostęp do bazy danych. Zwykle patrzę na kod i mówię: „To robi zapytania n + 1, powinieneś to zmienić, aby zrobić tylko 1 lub 2”

Ponieważ wszystkie moje dane są odczytywane z bazy danych i pokazywane użytkownikowi, staram się minimalizować ilość danych, z którymi pracuję, do tego stopnia, że ​​różnica między algorytmem liniowym a algorytmem O (n ^ 2) jest dość duża nieistotny.

Jeśli wystąpi problem, profilujemy go i naprawimy później.

Greg
źródło
1
Właściwie uważam, że ta zwyczajna kwestia „n + 1” jest dość niebezpieczna. W szczególności widziałem kod, który powodował, że zapytania n ^ d (gdzie d> = 2) zostały odrzucone jako „n + 1”, co sprawiło, że naprawdę okropna sytuacja wyglądała po prostu źle.
philosodad
3

Trzy pytania, które stawiasz i myślę, że krótkie odpowiedzi mogą pomóc w dłuższych argumentach podanych do tej pory.

Jak istotny jest ten test dla rozwoju przemysłu?

Zależy od branży.

Wszędzie tam, gdzie problemem jest szybkość kodu lub przestrzeń kodu, jest to całkowicie istotne dla branży. Często musisz wiedzieć, ile czasu zajmie procedura lub ile zajmie pamięci (w trybie offline / offline).

Jak często korzystasz z niego?

Zależy od branży.

Jeśli wydajność i skalowanie nie mają większego znaczenia dla wykonywanego zadania, rzadko, tylko wtedy, gdy występuje poważny niedobór wydajności. Jeśli jesteś inżynierem bardzo używanego systemu krytycznego, prawdopodobnie na co dzień.

Jak konieczne jest wyuczone podejście do problemu?

Całkowicie konieczne.

Być może będziesz musiał używać go codziennie lub tylko w tragicznych okolicznościach; ale czasami będzie to potrzebne. Najlepiej podczas projektowania, zanim pojawi się problem, niż rozpaczliwie profilować system dławienia.

Orbling
źródło
3

Powiedziałbym, że to bardzo często. Zasadniczo nie udowadniamy, że coś ma konkretny duży O, ale zinternalizowaliśmy ten pomysł i zapamiętaliśmy / zapoznaliśmy się z gwarancjami dużego O dla określonych struktur danych i algorytmów i wybieramy te najszybsze do określonego zastosowania. Pomaga mieć bibliotekę pełną wszystkich opcji, taką jak biblioteka kolekcji Java lub C ++ STL. Domyślnie i naturalnie używasz big-O każdego dnia, kiedy decydujesz się użyć java.util.HashMap( O(1)odnośnika) zamiast java.util.TreeMap( O(lg n)odnośnika) i na pewno zdecydujesz się nie uruchamiać wyszukiwania liniowego w java.util.LinkedList( O(n)odnośniku) czegoś, co nie wymaga posortowanego dostępu.

Kiedy ktoś wybiera nieoptymalną implementację, a ktoś, kto wie lepiej, przychodzi i widzi swój kod, częścią naszego słownika jest ich poprawianie ”, twoja implementacja zajmuje kwadratowy czas, ale możemy to sprowadzić do n-log-n, wykonując to w ten sposób zamiast tego ”tak naturalnie i automatycznie, jak przy użyciu języka angielskiego, aby zamówić pizzę.

Ken Bloom
źródło
3

tak

Być może nie musisz przeprowadzać formalnych analiz, ale zrozumienie co do kolejności złożoności algorytmu - i jak porównać dwa algorytmy wokół niego - ma kluczowe znaczenie, jeśli chcesz wykonywać nietrywialne prace i sprawić, by dobrze się sprawdził.

Pracowałem na dwóch różnych systemach, które wydawały się dobre na wczesnym etapie rozwoju, ale sprowadziłem sprzęt na kolana w testach produkcyjnych, ponieważ ktoś użył algorytmu O (n ^ 2). W obu przypadkach poprawka była trywialną zmianą w algorytmie O (n).

Bob Murphy
źródło
1

Prawdopodobnie jest używany w miejscach, w których opracowują interfejsy API do konsumpcji. C ++ STL jest jednym z niewielu interfejsów API, które mają ograniczenia złożoności nałożone na jego algorytmy. Ale dla codziennego pracującego programisty / starszego programisty / projektanta / architekta nie przychodzi im to do głowy.

sashang
źródło
Każdy dobry interfejs API do gromadzenia danych zapewnia te gwarancje, na przykład interfejs API do kolekcji Java również zawiera te gwarancje w swojej dokumentacji.
Ken Bloom
1

Nie uważam tego za ważne poza komunikowaniem pomysłów i pracuję w obszarach krytycznych pod względem wydajności (raytracing, przetwarzanie obrazu i siatki, systemy cząstek, silniki fizyki itp.) I musiałem opracować wiele zastrzeżonych algorytmów i struktur danych podczas pracy w R&D. W tych obszarach często garstka bardzo wydajnych struktur danych i algorytmów może przynieść zupełnie nowe, najnowocześniejsze produkty, podczas gdy wczorajsze algorytmy powodują, że istniejące produkty stają się przestarzałe, dlatego zawsze dąży się do robienia rzeczy bardziej wydajnie. Jednak z zastrzeżeniem, nigdy nie opublikowałem żadnych artykułów na temat opracowanych przeze mnie algorytmów. Wszystkie były zastrzeżone. Gdybym to zrobił, potrzebowałbym pomocy matematyka, aby sformułować dowody i tak dalej.

Jednak moim zdaniem ilość pracy obliczeniowej na iterację jest często bardziej bezpośrednia niż skalowalność algorytmu, chyba że algorytm skaluje się naprawdę słabo. Jeśli ktoś wymyśli najnowocześniejszą technikę raytracingu, bardziej interesują mnie techniki obliczeniowe, takie jak sposób reprezentowania i dostępu do danych niż złożoność algorytmiczna, ponieważ rozsądna skalowalność jest już zapewniona w tym konkurencyjnym i innowacyjnym scenariuszu. Nie możesz być konkurencyjny wymyślając algorytmy, które nie skalują się.

Oczywiście, jeśli porównujesz złożoność kwadratową do liniowej, to ogromna różnica. Ale większość ludzi w mojej dziedzinie jest wystarczająco kompetentna, aby uniknąć zastosowania algorytmu złożoności kwadratowej do imponujących danych wejściowych. Skalowalność jest często głęboko implikowana, a bardziej znaczące i interesujące pytania brzmią: „Czy korzystałeś z GPGPU? SIMD? Czy działa równolegle? Jak reprezentowałeś dane? Czy zreorganizowałeś je dla wzorców dostępu przyjaznych dla pamięci podręcznej? Jak zajmuje dużo pamięci? Czy może solidnie poradzić sobie z tą sprawą? Czy odraczasz pewne przetwarzanie czy robisz to za jednym razem?

Nawet algorytm liniowo-rytmiczny może przewyższyć algorytm liniowo-czasowy, jeśli ten pierwszy uzyskuje dostęp do pamięci w bardziej optymalny sposób, np. Lub lepiej nadaje się do wielowątkowości i / lub SIMD. Czasami nawet algorytm liniowy może przewyższyć algorytm logarytmiczny z tych powodów, a naturalnie algorytmy czasu liniowego przewyższają algorytmy logarytmiczne dla małych wejść.

Dlatego dla mnie ważniejsze są to, co niektórzy nazywają „mikrooptymalizacjami”, takie jak reprezentacje danych (układy pamięci, wzorce dostępu z podziałem pól gorących / zimnych itp.), Wielowątkowość, SIMD, a czasami GPGPU. W dziedzinie, w której wszyscy są już wystarczająco kompetentni, aby używać przyzwoitych i najnowocześniejszych algorytmów do wszystkiego, a nowe artykuły są publikowane przez cały czas, twoja przewaga konkurencyjna w pokonaniu algorytmów nie polega na poprawie złożoności algorytmicznej, ale na bardziej bezpośredniej wydajność obliczeniowa.

Moje pole jest zdominowane przez genialnych matematyków, ale nie zawsze tych, którzy znają obliczeniowy koszt tego, co robią lub wiele sztuczek na niższym poziomie, aby przyspieszyć kod. To zazwyczaj moja przewaga nad nimi w opracowywaniu szybszych i węższych algorytmów i struktur danych, mimo że moje są o wiele mniej skomplikowane. Bawię się tym, co lubi sprzęt, w stronę bitów i bajtów i sprawia, że ​​każda iteracja pracy jest znacznie tańsza, nawet jeśli wykonuję kilka kolejnych iteracji pracy niż naprawdę wyrafinowany algorytm - praca w moim przypadku jest znacznie tańsza. Kod, który piszę, również jest o wiele prostszy. Jeśli ludzie uważają, że mikrooptymalizowane wersje prostych algorytmów i struktur danych są trudne do zrozumienia i utrzymania,

Jako podstawowy przykład wymyśliłem prostą strukturę siatki, która ostatecznie przewyższyła drzewo KD w naszej firmie w zakresie wykrywania kolizji i usuwania zbędnych punktów. Moja głupia, prymitywna siatka była o wiele mniej skomplikowana algorytmicznie i jestem głupsza matematycznie i algorytmicznie niż facet, który zaimplementował drzewo KD w swoim nowatorskim sposobie znajdowania punktu środkowego, ale właśnie dostroiłem pamięć mojej siatki i wzorce dostępu oraz to wystarczyło, by przewyższyć coś znacznie bardziej wyrafinowanego.

Inną zaletą, która pozwala mi przetrwać na polu zdominowanym przez ludzi znacznie mądrzejszych ode mnie, jest po prostu zrozumienie, w jaki sposób działa użytkownik, ponieważ używam oprogramowania, które rozwijam w ten sam sposób. To daje mi pomysły na algorytmy, które naprawdę natychmiast dostosowują się do zainteresowań użytkowników. Jako podstawowy przykład większość ludzi próbuje przyspieszyć takie rzeczy, jak wykrywanie kolizji za pomocą indeksowania przestrzennego. Prawie kilkadziesiąt lat temu poczyniłem prostą obserwację kształtującą karierę dla modeli organicznych, które na przykład, jeśli postać położy dłonie na twarzy, struktura indeksowania przestrzennego będzie musiała rozdzielić węzły i dokonać drogich aktualizacji, jeśli postać potem zdjął rękę z twarzy. Jeśli zamiast tego partycjonujesz na podstawie danych łączności, a nie pozycji wierzchołków, możesz uzyskać stabilną strukturę hierarchiczną, która aktualizuje się bardzo szybko i nigdy nie musi dzielić ani ponownie równoważyć drzewa (musi tylko aktualizować obwiednię w każdej klatce animacji) ... takie rzeczy - algorytmuje dziecko bez ciężkiego tła matematycznego mogliby wymyślić, gdyby po prostu zrozumieli podstawową koncepcję, ale ci, którzy wymykali się matematykom, ponieważ nie myśleli o rzeczach w sposób tak bliski jak pracowali użytkownicy i zbyt dużo myśleli o właściwościach geometrii, a nie o geometrii był powszechnie używany. Dobrze sobie radzę, opierając się bardziej na ogólnej wiedzy obliczeniowej i wiedzy użytkownika końcowego niż na algorytmach. W każdym razie tak naprawdę nie uważałem za tak ważne skupienie się na złożoności algorytmicznej.

204677
źródło
0

Tak, złożoność ma znaczenie w branży. Jeśli w końcu zaprojektujesz coś, w którym ścieżka krytyczna skaluje się jako N-kwadrat (podwojenie liczby czegoś powoduje, że system jest czterokrotnie obciążony), uderzysz w wąskie gardło skalowania znacznie szybciej niż jeśli masz coś, co skaluje się w N.

Jednak zwykle nie jest to robione jako właściwy, formalny dowód, że coś ma określoną złożoność, więc posiadanie dobrej intuicji co do złożoności wzoru operacji jest dobrym początkiem.

Vatine
źródło
0

Nigdy nie myślę o wielkim O w perspektywie matematycznej, nigdy nie myślę o wielkim O, chyba że o to poproszę. Po prostu widzę algorytm w mojej głowie i mogę stwierdzić, czy jest zły, ponieważ wykonuje wiele pętli w pamięci dla każdego N, czy dzieli i podbija lub coś w tym rodzaju. W razie potrzeby mogę to przełożyć na dużą notację O w kilka sekund, ale łatwiej mi po prostu wiedzieć, jak algorytm / kontener działa z pamięcią, niż myśleć o matematycznej perspektywie.

Koder
źródło
-3

Pytania zadawane w wywiadach mają na celu sprawdzenie, czy potrafisz wyjaśnić i logicznie myśleć . Ankieter próbuje również dowiedzieć się, czy możesz wykorzystać to, co wiesz, aby rozwiązać związany z tym problem .

Każdy, kto poświęcił jakieś wartościowe studium inżynierii oprogramowania, zetknie się z „Big O”, aby odpowiedzieć na dobre pytanie o „Big O”, musisz także zrozumieć standardowe struktury danych i algorytmy.

Podczas rozmowy z pracownikiem poszukujesz kogoś, kto szybko nauczy się pracy, a nie kogoś, kto zna dany zestaw szczegółowych umiejętności, więc może być bardzo trudno wybrać pytania, które zarówno ankieter, jak i ankieter mają wspólne zrozumienie z.

Zatem pytania dotyczące „dużego O” mogą być bardzo istotne w procesie wywiadu.

Przynajmniej co roku przez długi czas jako programista musiałem naprawiać powolny kod, ponieważ ktoś nie rozumie poprawnych struktur danych i algorytmów, ale możesz rozwiązać te problemy bez szczegółowego zrozumienia Big O. Jednak ludzie, którzy rozumieją namiot Big O, nie unikają tych problemów.

Ian
źródło