Bir partide herkesin tan\u0131d\u0131\u011f\u0131 ama kendisi kimseyi tan\u0131mayan o gizemli ki\u015fiyi bulmak hi\u00e7 d\u00fc\u015f\u00fcnd\u00fcn\u00fcz m\u00fc? Veya bir sosyal a\u011fda herkesin g\u00fcvendi\u011fi ancak kendisi kimseye g\u00fcvenmeyen bir otoriteyi? \u0130\u015fte bu senaryolar, bilgisayar bilimlerinde “\u00dcnl\u00fc Problemi” (The Celebrity Problem) olarak bilinen ilgin\u00e7 bir algoritmik bulmacan\u0131n temelini olu\u015fturur. Bu problem, bize sadece do\u011fru \u00e7\u00f6z\u00fcm\u00fc bulman\u0131n de\u011fil, ayn\u0131 zamanda en verimli \u00e7\u00f6z\u00fcm\u00fc tasarlaman\u0131n ne kadar \u00f6nemli oldu\u011funu g\u00f6sterir. Bu makalede, \u00dcnl\u00fc Problemi’nin ne oldu\u011funu, basit kaba kuvvet yakla\u015f\u0131mlar\u0131ndan ba\u015flayarak, b\u00fcy\u00fck veri k\u00fcmelerinde bile \u0131\u015f\u0131k h\u0131z\u0131nda \u00e7al\u0131\u015fabilen O(n) zaman karma\u015f\u0131kl\u0131\u011f\u0131na sahip optimize edilmi\u015f \u00e7\u00f6z\u00fcmlere nas\u0131l ula\u015ft\u0131\u011f\u0131m\u0131z\u0131 ad\u0131m ad\u0131m inceleyece\u011fiz. Algoritmik d\u00fc\u015f\u00fcnme yetene\u011finizi geli\u015ftirmek ve veri yap\u0131lar\u0131yla daha derin bir ba\u011f kurmak i\u00e7in haz\u0131r olun.<\/p>\n
Hayal edin, kalabal\u0131k bir partidesiniz ve kat\u0131l\u0131mc\u0131lar aras\u0131nda bir “\u00fcnl\u00fc” var. Bu \u00fcnl\u00fc, partideki herkes taraf\u0131ndan tan\u0131n\u0131yor. Ancak ilgin\u00e7 bir \u015fekilde, bu \u00fcnl\u00fc kimseyi tan\u0131m\u0131yor. Yani, bir \u00fcnl\u00fc, di\u011fer t\u00fcm insanlarla tek y\u00f6nl\u00fc bir tan\u0131\u015f\u0131kl\u0131k ili\u015fkisine sahip: herkes onu tan\u0131r, ama o kimseyi tan\u0131maz. Peki, bu \u00fcnl\u00fcy\u00fc sadece “kim kimi tan\u0131yor?” sorular\u0131 sorarak nas\u0131l bulabiliriz? \u0130\u015fte \u00dcnl\u00fc Problemi’nin \u00f6z\u00fc tam olarak budur.<\/p>\n
Bu problem, bilgisayar bilimleri ve algoritma tasar\u0131m\u0131nda s\u0131k\u00e7a kar\u015f\u0131la\u015f\u0131lan klasik bir sorundur. Amac\u0131m\u0131z, en az say\u0131da soru sorarak veya en az i\u015flem yaparak bu \u00fcnl\u00fcy\u00fc tespit etmektir. Problem genellikle bir grup insan\u0131n oldu\u011fu ve aralar\u0131ndaki “tan\u0131ma” ili\u015fkilerinin bilindi\u011fi bir senaryoda ortaya konur. Bu ili\u015fkiler genellikle bir kom\u015fuluk matrisi (adjacency matrix) veya kom\u015fuluk listesi (adjacency list) gibi veri yap\u0131lar\u0131 kullan\u0131larak temsil edilir. \u00d6rne\u011fin, N ki\u015filik bir grupta, e\u011fer ki\u015fi A, ki\u015fi B’yi tan\u0131yorsa, bu bilgi matriste Bu ko\u015fullar, \u00fcnl\u00fcy\u00fc di\u011ferlerinden ay\u0131ran belirgin \u00f6zelliklerdir. E\u011fer b\u00f6yle bir ki\u015fi varsa, onu bulmam\u0131z gerekir; e\u011fer yoksa, olmad\u0131\u011f\u0131n\u0131 belirtmeliyiz. Bu problem, \u00f6zellikle \u00e7izge (graph) teorisi ve algoritmalar\u0131n verimlili\u011fi konular\u0131nda temel bir anlay\u0131\u015f geli\u015ftirmenize yard\u0131mc\u0131 olur. Ayr\u0131ca, ger\u00e7ek d\u00fcnya senaryolar\u0131nda, \u00f6rne\u011fin bir a\u011fdaki merkezi bir g\u00fcven kayna\u011f\u0131n\u0131 bulmak veya bir sistemdeki ba\u011f\u0131ml\u0131l\u0131klar\u0131 \u00e7\u00f6zmek gibi durumlarda da benzer mant\u0131klar kullan\u0131labilir. \u015eimdi, bu \u00fcnl\u00fcy\u00fc bulmak i\u00e7in ilk ve en basit yakla\u015f\u0131m olan kaba kuvvet \u00e7\u00f6z\u00fcm\u00fcne ge\u00e7elim.<\/p>\n \u00dcnl\u00fc problemini daha iyi anlayabilmek i\u00e7in, \u00f6ncelikle problemdeki temel kavramlar\u0131 ve varsay\u0131mlar\u0131 netle\u015ftirmemiz gerekiyor. Bu problem genellikle, belirli say\u0131da ki\u015finin oldu\u011fu ve bu ki\u015filer aras\u0131ndaki “tan\u0131ma” ili\u015fkilerinin tan\u0131mland\u0131\u011f\u0131 bir senaryo \u00fczerinden i\u015flenir. Bu ili\u015fkiler, algoritmik olarak nas\u0131l temsil edilir ve bu temsil, \u00e7\u00f6z\u00fcme ula\u015fmam\u0131zda nas\u0131l bir rol oynar? Gelin bu sorulara yan\u0131t arayal\u0131m.<\/p>\n Problemi \u00e7\u00f6zmek i\u00e7in, kimin kimi tan\u0131d\u0131\u011f\u0131n\u0131 bilmemiz gerekir. Bu bilgi genellikle ikili bir matris (boolean matrix) veya bir \u00e7izge (graph) yap\u0131s\u0131 kullan\u0131larak saklan\u0131r. En yayg\u0131n kullan\u0131lan y\u00f6ntemlerden biri, \u00d6rnek bir senaryo d\u00fc\u015f\u00fcnelim: D\u00f6rt ki\u015filik bir grup var: Alice (0), Bob (1), Carol (2), David (3). Tan\u0131\u015f\u0131kl\u0131k matrisi \u015f\u00f6yle olsun:<\/p>\n Bu matrise g\u00f6re, Carol (2) bir \u00fcnl\u00fc olabilir mi? Bakal\u0131m:<\/p>\n G\u00f6rd\u00fc\u011f\u00fcm\u00fcz gibi, Carol (2) hem kimseyi tan\u0131m\u0131yor hem de herkes onu tan\u0131yor. Dolay\u0131s\u0131yla, bu \u00f6rnekte Carol bir \u00fcnl\u00fcd\u00fcr. Bu temel temsil ve \u00fcnl\u00fc tan\u0131m\u0131, kaba kuvvetten optimize edilmi\u015f \u00e7\u00f6z\u00fcmlere kadar t\u00fcm yakla\u015f\u0131mlar\u0131m\u0131z\u0131n temelini olu\u015fturacakt\u0131r. \u015eimdi, bu matrisi kullanarak \u00fcnl\u00fcy\u00fc bulman\u0131n en basit yolu olan kaba kuvvet \u00e7\u00f6z\u00fcm\u00fcn\u00fc inceleyelim.<\/p>\n \u00dcnl\u00fc problemini \u00e7\u00f6zmek i\u00e7in akla gelen ilk ve en do\u011fal yakla\u015f\u0131m, her bir ki\u015fiyi potansiyel bir \u00fcnl\u00fc aday\u0131 olarak ele al\u0131p, \u00fcnl\u00fc olma ko\u015fullar\u0131n\u0131 tek tek kontrol etmektir. Bu y\u00f6nteme “kaba kuvvet” (brute force) \u00e7\u00f6z\u00fcm\u00fc denir. Mant\u0131\u011f\u0131 olduk\u00e7a basittir: gruptaki her bir ki\u015fi i\u00e7in iki kontrol yapar\u0131z:<\/p>\n E\u011fer bir ki\u015fi bu iki ko\u015fulu da ayn\u0131 anda sa\u011fl\u0131yorsa, o ki\u015fi \u00fcnl\u00fcd\u00fcr. Bu kontrol\u00fc gruptaki her bir ki\u015fi i\u00e7in s\u0131rayla yapar\u0131z. E\u011fer bir \u00fcnl\u00fc bulursak, o ki\u015fiyi d\u00f6nd\u00fcr\u00fcr\u00fcz. E\u011fer t\u00fcm ki\u015fileri kontrol ettikten sonra hala bir \u00fcnl\u00fc bulamam\u0131\u015fsak, grupta \u00fcnl\u00fc olmad\u0131\u011f\u0131n\u0131 belirtiriz.<\/p>\n Bu yakla\u015f\u0131m\u0131n nas\u0131l \u00e7al\u0131\u015ft\u0131\u011f\u0131n\u0131 daha detayl\u0131 inceleyelim. Diyelim ki Yukar\u0131daki pseudocode’da g\u00f6rd\u00fc\u011f\u00fcn\u00fcz gibi, her bir potansiyel \u00fcnl\u00fc aday\u0131 i\u00e7in iki i\u00e7 d\u00f6ng\u00fc bulunmaktad\u0131r. \u0130lk d\u00f6ng\u00fc, aday\u0131n kimseyi tan\u0131mad\u0131\u011f\u0131ndan emin olmak i\u00e7in Kaba kuvvet \u00e7\u00f6z\u00fcm\u00fcn\u00fcn \u0130ki ki\u015fi, diyelim ki A ve B aras\u0131ndaki tan\u0131\u015f\u0131kl\u0131k ili\u015fkisini sorgulad\u0131\u011f\u0131m\u0131zda, d\u00f6rt olas\u0131 senaryo ortaya \u00e7\u0131kar ve her biri bize de\u011ferli bilgiler sunar:<\/p>\n Bu temel \u00e7\u0131kar\u0131mlar, tek bir sorgu ile en az bir ki\u015fiyi \u00fcnl\u00fc adaylar\u0131 listesinden \u00e7\u0131karabilece\u011fimiz anlam\u0131na gelir. E\u011fer her sorgu bir ki\u015fiyi elerse ve Y\u0131\u011f\u0131n tabanl\u0131 yakla\u015f\u0131mda, ba\u015flang\u0131\u00e7ta t\u00fcm ki\u015fileri bir y\u0131\u011f\u0131na ekleriz. Ard\u0131ndan, y\u0131\u011f\u0131n bo\u015falana veya y\u0131\u011f\u0131nda sadece bir ki\u015fi kalana kadar a\u015fa\u011f\u0131daki ad\u0131mlar\u0131 tekrarlar\u0131z:<\/p>\n Bu s\u00fcre\u00e7 sonunda y\u0131\u011f\u0131nda ya bir ki\u015fi kal\u0131r ya da y\u0131\u011f\u0131n bo\u015fal\u0131r. E\u011fer y\u0131\u011f\u0131nda bir ki\u015fi kal\u0131rsa, bu ki\u015fi potansiyel \u00fcnl\u00fc aday\u0131m\u0131zd\u0131r. Y\u0131\u011f\u0131n bo\u015fal\u0131rsa, \u00fcnl\u00fc yoktur. Y\u0131\u011f\u0131nda kalan bu tek aday\u0131 (diyelim ki Bu algoritman\u0131n zaman karma\u015f\u0131kl\u0131\u011f\u0131na bakt\u0131\u011f\u0131m\u0131zda: y\u0131\u011f\u0131n i\u015flemleri (push\/pop) her bir ki\u015fi i\u00e7in en fazla iki kez yap\u0131l\u0131r, bu da Y\u0131\u011f\u0131n kullanmadan da benzer bir mant\u0131kla Bu d\u00f6ng\u00fc bitti\u011finde, Her iki \u00dcnl\u00fc Problemi, ilk bak\u0131\u015fta sadece bir parti oyununa benzese de, alt\u0131nda yatan mant\u0131k ve \u00e7\u00f6z\u00fcm stratejileri, ger\u00e7ek d\u00fcnyadaki bir\u00e7ok karma\u015f\u0131k problemi \u00e7\u00f6zmek i\u00e7in kullan\u0131labilir. Algoritman\u0131n soyut yap\u0131s\u0131, farkl\u0131 ba\u011flamlara kolayca adapte edilebilir. \u0130\u015fte \u00dcnl\u00fc Problemi'nin ilham verdi\u011fi veya do\u011frudan uyguland\u0131\u011f\u0131 baz\u0131 ger\u00e7ek d\u00fcnya senaryolar\u0131 ve vaka analizleri:<\/p>\n Sosyal medya platformlar\u0131nda veya di\u011fer a\u011f tabanl\u0131 sistemlerde, \"\u00fcnl\u00fc\" kavram\u0131, g\u00fcvenilir bir otorite veya bilgi kayna\u011f\u0131 olarak yorumlanabilir. Bir \u00fcnl\u00fcy\u00fc, herkesin takip etti\u011fi (tan\u0131d\u0131\u011f\u0131) ancak kendisi \u00e7ok az ki\u015fiyi takip eden (tan\u0131yan) bir hesap olarak d\u00fc\u015f\u00fcnebiliriz. \u00d6rne\u011fin, bir haber ajans\u0131n\u0131n resmi Twitter hesab\u0131 veya bir devlet kurumunun duyuru sayfas\u0131 bu tan\u0131ma uyabilir. Bu t\u00fcr bir \"\u00fcnl\u00fc\" hesab\u0131 bulmak, bilgi ak\u0131\u015f\u0131n\u0131 analiz etmek, sahte haberleri tespit etmek veya en etkili bilgi kaynaklar\u0131n\u0131 belirlemek i\u00e7in kritik olabilir. Algoritma, a\u011fdaki en merkezi ve g\u00fcvenilir d\u00fc\u011f\u00fcm\u00fc (node) bulmaya yard\u0131mc\u0131 olur.<\/p>\n Yaz\u0131l\u0131m geli\u015ftirmede, mod\u00fcller veya k\u00fct\u00fcphaneler aras\u0131nda ba\u011f\u0131ml\u0131l\u0131klar bulunur. Bir mod\u00fcl\u00fcn \u00e7al\u0131\u015fmas\u0131 i\u00e7in ba\u015fka bir mod\u00fcle ihtiya\u00e7 duymas\u0131, \"tan\u0131ma\" ili\u015fkisine benzetilebilir. E\u011fer bir mod\u00fcl, herhangi bir ba\u015fka mod\u00fcle ba\u011f\u0131ml\u0131 de\u011filse (kimseyi tan\u0131m\u0131yor) ama di\u011fer t\u00fcm mod\u00fcller bir \u015fekilde ona ba\u011f\u0131ml\u0131ysa (herkes onu tan\u0131yor), bu mod\u00fcl \"\u00fcnl\u00fc\" bir \u00e7ekirdek (core) mod\u00fcl olabilir. Bu, bir projenin temelini olu\u015fturan, en az d\u0131\u015f ba\u011f\u0131ml\u0131l\u0131\u011f\u0131 olan ancak di\u011fer her \u015feyin \u00fczerine in\u015fa edildi\u011fi bir bile\u015feni bulmak i\u00e7in kullan\u0131labilir. \u00d6rne\u011fin, bir i\u015fletim sisteminin \u00e7ekirde\u011fi (kernel) veya bir yaz\u0131l\u0131m \u00e7er\u00e7evesinin (framework) ana mod\u00fcl\u00fc bu tan\u0131ma uyabilir. Bu t\u00fcr bir \"\u00fcnl\u00fc\" mod\u00fcl\u00fc belirlemek, sistemin mimarisini anlamak, potansiyel zay\u0131fl\u0131klar\u0131 tespit etmek veya refakt\u00f6ring (yeniden d\u00fczenleme) kararlar\u0131 almak i\u00e7in faydal\u0131d\u0131r.<\/p>\n Bir organizasyon i\u00e7indeki eri\u015fim kontrol sistemlerinde, belirli bir kullan\u0131c\u0131n\u0131n veya rol\u00fcn \"\u00fcnl\u00fc\" stat\u00fcs\u00fcnde olmas\u0131 d\u00fc\u015f\u00fcn\u00fclebilir. \u00d6rne\u011fin, bir sistem y\u00f6neticisi veya belirli bir yetki rol\u00fc, di\u011fer t\u00fcm kullan\u0131c\u0131lar taraf\u0131ndan \"tan\u0131n\u0131yor\" (yani, o rol\u00fcn yetkileri herkesi etkiliyor) ancak kendisi di\u011fer kullan\u0131c\u0131lar\u0131n yetkilerini do\u011frudan \"tan\u0131m\u0131yor\" (yani, di\u011ferlerinin yetkileri onun yetkilerini do\u011frudan etkilemiyor) olabilir. Bu, sistemdeki en y\u00fcksek yetkiye sahip ve en kritik eri\u015fim noktalar\u0131n\u0131 belirlemek i\u00e7in kullan\u0131labilir. Bu t\u00fcr bir \"\u00fcnl\u00fc\" varl\u0131\u011f\u0131n tespiti, g\u00fcvenlik a\u00e7\u0131klar\u0131 veya yetki ihlallerini \u00f6nlemede \u00f6nemli bir rol oynayabilir.<\/p>\n B\u00fcy\u00fck veritabanlar\u0131nda, tablolar aras\u0131 ili\u015fkiler (foreign keys) \"tan\u0131ma\" ili\u015fkisi gibi d\u00fc\u015f\u00fcn\u00fclebilir. E\u011fer bir tablo, di\u011fer t\u00fcm tablolar taraf\u0131ndan referans veriliyor (herkes onu tan\u0131yor) ancak kendisi ba\u015fka hi\u00e7bir tabloya referans vermiyorsa (kimseyi tan\u0131m\u0131yor), bu tablo bir \"\u00fcnl\u00fc\" tablo olabilir. Bu t\u00fcr tablolar genellikle ana veri tablolar\u0131d\u0131r ve sistemin \u00e7ekirde\u011fini olu\u015fturur. Bu tablolar\u0131n belirlenmesi, veritaban\u0131 \u015femas\u0131n\u0131 optimize etmek, sorgu performans\u0131n\u0131 art\u0131rmak veya veri b\u00fct\u00fcnl\u00fc\u011f\u00fcn\u00fc sa\u011flamak i\u00e7in \u00f6nemlidir. \u00d6rne\u011fin, bir m\u00fc\u015fteri tablosu veya \u00fcr\u00fcn katalo\u011fu tablosu genellikle bu nitelikte olabilir.<\/p>\n G\u00f6r\u00fcld\u00fc\u011f\u00fc gibi, \u00dcnl\u00fc Problemi sadece teorik bir bulmaca olmaktan \u00f6te, soyutlanm\u0131\u015f haliyle bir\u00e7ok pratik uygulama alan\u0131 bulan g\u00fc\u00e7l\u00fc bir algoritmik konsepttir. Algoritmik d\u00fc\u015f\u00fcnme, bu t\u00fcr problemlerin temelini anlay\u0131p farkl\u0131 senaryolara uyarlayabilme yetene\u011fini geli\u015ftirir.<\/p>\n Her algoritmada oldu\u011fu gibi, \u00dcnl\u00fc Problemi'nin \u00e7\u00f6z\u00fcm\u00fcnde de baz\u0131 \"k\u00f6\u015fe durumlar\" (edge cases) ve dikkate al\u0131nmas\u0131 gereken \u00f6zel senaryolar vard\u0131r. Bu durumlar\u0131 do\u011fru bir \u015fekilde ele almak, algoritman\u0131n sa\u011flaml\u0131\u011f\u0131n\u0131 ve g\u00fcvenilirli\u011fini art\u0131r\u0131r. Ayr\u0131ca, performans\u0131 daha da optimize etmek i\u00e7in baz\u0131 ipu\u00e7lar\u0131 da mevcuttur.<\/p>\n En temel k\u00f6\u015fe durumlardan biri, grupta ger\u00e7ekten bir \u00fcnl\u00fc olmamas\u0131d\u0131r. \u00dcnl\u00fc Problemi'nin klasik tan\u0131m\u0131na g\u00f6re, bir grupta en fazla bir \u00fcnl\u00fc olabilir. Neden mi? Diyelim ki A ve B olmak \u00fczere iki farkl\u0131 \u00fcnl\u00fc var.<\/p>\n Bu iki durum (A, B'yi tan\u0131m\u0131yor ve B, A'y\u0131 tan\u0131m\u0131yor) ile (B, A'y\u0131 tan\u0131yor ve A, B'yi tan\u0131yor) \u00e7eli\u015fir. Dolay\u0131s\u0131yla, bir grupta birden fazla \u00fcnl\u00fc olamaz. Algoritmalar\u0131m\u0131z da bu nedenle en fazla bir potansiyel aday bulur.<\/p>\n E\u011fer grup bo\u015fsa ( Bu k\u00f6\u015fe durumlar\u0131 ve optimizasyon ipu\u00e7lar\u0131, algoritmik tasar\u0131mlar\u0131m\u0131z\u0131 daha sa\u011flam ve ger\u00e7ek d\u00fcnya ko\u015fullar\u0131na daha uygun hale getirmemize yard\u0131mc\u0131 olur. Her zaman, bir problemi \u00e7\u00f6zerken sadece \"mutlu yolu\" (happy path) de\u011fil, olas\u0131 t\u00fcm senaryolar\u0131 d\u00fc\u015f\u00fcnmek \u00f6nemlidir.<\/p>\n Bu makalede, \u00dcnl\u00fc Problemi'nin derinliklerine indik ve kaba kuvvet yakla\u015f\u0131m\u0131ndan ba\u015flayarak, \u00dcnl\u00fc Problemi, bize sadece bir algoritmay\u0131 de\u011fil, ayn\u0131 zamanda algoritmik d\u00fc\u015f\u00fcnme bi\u00e7imini de \u00f6\u011fretir. Bir problemi analiz etme, potansiyel \u00e7\u00f6z\u00fcmleri de\u011ferlendirme, verimsizlikleri tespit etme ve ard\u0131ndan daha zarif ve etkili \u00e7\u00f6z\u00fcmler tasarlama yetene\u011fi, her yaz\u0131l\u0131mc\u0131 ve m\u00fchendis i\u00e7in vazge\u00e7ilmez bir beceridir. Ger\u00e7ek d\u00fcnya senaryolar\u0131nda, sosyal a\u011f analizinden ba\u011f\u0131ml\u0131l\u0131k \u00e7\u00f6z\u00fcmlemeye, g\u00fcvenlik sistemlerinden veritaban\u0131 optimizasyonuna kadar bir\u00e7ok alanda benzer mant\u0131klar\u0131n kullan\u0131ld\u0131\u011f\u0131n\u0131 g\u00f6rd\u00fck. Bu, algoritmalar\u0131n soyut d\u00fcnyas\u0131n\u0131n somut problemlere nas\u0131l g\u00fc\u00e7l\u00fc \u00e7\u00f6z\u00fcmler sunabilece\u011finin \u00e7arp\u0131c\u0131 bir \u00f6rne\u011fidir.<\/p>\n Umar\u0131z bu makale, \u00dcnl\u00fc Problemi'ni anlaman\u0131za ve algoritmik d\u00fc\u015f\u00fcnme yetene\u011finizi geli\u015ftirmenize yard\u0131mc\u0131 olmu\u015ftur. Unutmay\u0131n, en iyi \u00e7\u00f6z\u00fcmler genellikle en basit olanlard\u0131r, ancak onlara ula\u015fmak i\u00e7in derinlemesine analiz ve yarat\u0131c\u0131 d\u00fc\u015f\u00fcnce gerekir.<\/p>\n \u00dcnl\u00fc Problemi neden \u00f6nemlidir?<\/strong><\/p>\n \u00dcnl\u00fc Problemi, algoritmik d\u00fc\u015f\u00fcnme, zaman karma\u015f\u0131kl\u0131\u011f\u0131 analizi ve optimizasyon tekniklerini anlamak i\u00e7in harika bir \u00f6rnektir. Ger\u00e7ek d\u00fcnyada sosyal a\u011f analizi, ba\u011f\u0131ml\u0131l\u0131k \u00e7\u00f6z\u00fcmlemesi ve g\u00fcvenlik sistemleri gibi bir\u00e7ok farkl\u0131 alanda benzer mant\u0131klar kullan\u0131l\u0131r.<\/p>\n<\/li>\n Bir grupta birden fazla \u00fcnl\u00fc olabilir mi?<\/strong><\/p>\n Hay\u0131r, \u00dcnl\u00fc Problemi'nin klasik tan\u0131m\u0131na g\u00f6re bir grupta en fazla bir \u00fcnl\u00fc olabilir. E\u011fer iki \u00fcnl\u00fc olsayd\u0131, her birinin di\u011ferini tan\u0131mamas\u0131, ancak herkesin onlar\u0131 tan\u0131mas\u0131 ko\u015fullar\u0131 \u00e7eli\u015firdi.<\/p>\n<\/li>\n \u00dcnl\u00fc Problemi i\u00e7in hangi veri yap\u0131lar\u0131 kullan\u0131labilir?<\/strong><\/p>\n Tan\u0131\u015f\u0131kl\u0131k ili\u015fkilerini temsil etmek i\u00e7in genellikle bir kom\u015fuluk matrisi (adjacency matrix) kullan\u0131l\u0131r. \u00c7\u00f6z\u00fcm algoritmas\u0131 taraf\u0131nda ise, #Algoritma #VeriYap\u0131lar\u0131 #BilgisayarBilimi #Optimizasyon #Yaz\u0131l\u0131mGeli\u015ftirme<\/p>\n","protected":false},"excerpt":{"rendered":"Bir partide herkesin tan\u0131d\u0131\u011f\u0131 ama kendisi kimseyi tan\u0131mayan o gizemli ki\u015fiyi bulmak hi\u00e7 d\u00fc\u015f\u00fcnd\u00fcn\u00fcz m\u00fc? Veya bir sosyal a\u011fda herkesin g\u00fcvendi\u011fi ancak kendisi kimseye g\u00fcvenmeyen bir otoriteyi?","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"csco_page_header_type":"","csco_page_load_nextpost":"","csco_page_subscribe_form":"","csco_page_contact_form":"","footnotes":""},"categories":[1],"tags":[],"class_list":{"0":"post-45147","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-genel","7":"cs-entry","8":"cs-video-wrap"},"yoast_head":"\nmatris[A][B] = True<\/code> \u015feklinde ifade edilebilir. Bir \u00fcnl\u00fcy\u00fc tan\u0131mlayan iki temel ko\u015ful vard\u0131r:<\/p>\n\n
N-1<\/code> ki\u015finin tamam\u0131 onu tan\u0131r.<\/li>\nN-1<\/code> ki\u015fiden hi\u00e7birini tan\u0131maz.<\/li>\n<\/ul>\n\u00dcnl\u00fc Probleminin Temelleri: Kim Kimi Tan\u0131yor?<\/h2>\n
N x N<\/code> boyutlar\u0131nda bir kom\u015fuluk matrisi kullanmakt\u0131r. Bu matriste, matris[i][j]<\/code> de\u011feri, i<\/code> ki\u015finin j<\/code> ki\u015fiyi tan\u0131y\u0131p tan\u0131mad\u0131\u011f\u0131n\u0131 belirtir. E\u011fer i<\/code>, j<\/code>‘yi tan\u0131yorsa, matris[i][j] = True<\/code> (veya 1) olur; aksi takdirde False<\/code> (veya 0) olur. Kendi kendini tan\u0131ma durumu genellikle problem tan\u0131m\u0131n\u0131n d\u0131\u015f\u0131ndad\u0131r veya matris[i][i] = False<\/code> olarak kabul edilir. Bu matris, problemdeki t\u00fcm tan\u0131\u015f\u0131kl\u0131k ili\u015fkilerini \u00f6zetler niteliktedir.<\/p>\n\n \/\/ 0 1 2 3 (Alice, Bob, Carol, David)\n \/\/ 0 [F, T, T, T] Alice Bob'u, Carol'\u0131, David'i tan\u0131yor.\n \/\/ 1 [F, F, T, F] Bob sadece Carol'\u0131 tan\u0131yor.\n \/\/ 2 [F, F, F, F] Carol kimseyi tan\u0131m\u0131yor.\n \/\/ 3 [F, T, T, F] David Bob'u ve Carol'\u0131 tan\u0131yor.\n <\/code><\/pre>\n\n
False<\/code>. Bu, \u00fcnl\u00fcn\u00fcn ikinci ko\u015fulunu sa\u011fl\u0131yor.<\/li>\n\n
matris[0][2] = True<\/code>. Evet.<\/li>\nmatris[1][2] = True<\/code>. Evet.<\/li>\nmatris[3][2] = True<\/code>. Evet.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\nKaba Kuvvet \u00c7\u00f6z\u00fcm\u00fc: Herkesi Tek Tek Kontrol Etmek (O(n^2))<\/h3>\n
\n
N<\/code> ki\u015filik bir grubumuz var ve tan\u0131\u015f\u0131kl\u0131k ili\u015fkilerini temsil eden bir tan\u0131yor(i, j)<\/code> fonksiyonumuz var. Bu fonksiyon, i<\/code> ki\u015finin j<\/code> ki\u015fiyi tan\u0131y\u0131p tan\u0131mad\u0131\u011f\u0131n\u0131 d\u00f6nd\u00fcr\u00fcr.<\/p>\n\n\/\/ Kaba Kuvvet \u00c7\u00f6z\u00fcm\u00fc \u0130\u00e7in Pseudocode\nfonksiyon findCelebrityBruteForce(N, tan\u0131yor):\n her ki\u015fi 'i' (0'dan N-1'e kadar) i\u00e7in:\n isCelebrity = True\n\n \/\/ Ko\u015ful 1: 'i' kimseyi tan\u0131m\u0131yor mu?\n her ki\u015fi 'j' (0'dan N-1'e kadar) i\u00e7in:\n e\u011fer i != j VE tan\u0131yor(i, j) == True ise:\n isCelebrity = False\n d\u00f6ng\u00fcy\u00fc k\u0131r (\u00e7\u00fcnk\u00fc 'i' zaten birini tan\u0131yor)\n \n \/\/ Ko\u015ful 2: Herkes 'i'yi tan\u0131yor mu?\n e\u011fer isCelebrity == True ise: \/\/ Sadece \u00f6nceki ko\u015ful sa\u011flan\u0131rsa kontrol et\n her ki\u015fi 'j' (0'dan N-1'e kadar) i\u00e7in:\n e\u011fer i != j VE tan\u0131yor(j, i) == False ise:\n isCelebrity = False\n d\u00f6ng\u00fcy\u00fc k\u0131r (\u00e7\u00fcnk\u00fc 'j', 'i'yi tan\u0131m\u0131yor)\n \n e\u011fer isCelebrity == True ise:\n d\u00f6n 'i' (\u00fcnl\u00fc bulundu)\n \n d\u00f6n -1 (\u00fcnl\u00fc bulunamad\u0131)\n <\/code><\/pre>\n<\/p><\/div>\nN-1<\/code> kontrol yapar. \u0130kinci d\u00f6ng\u00fc ise, di\u011fer herkesin aday\u0131 tan\u0131y\u0131p tan\u0131mad\u0131\u011f\u0131n\u0131 kontrol etmek i\u00e7in yine N-1<\/code> kontrol yapar. Bu i\u00e7 i\u00e7e d\u00f6ng\u00fcler nedeniyle, her bir aday i\u00e7in yakla\u015f\u0131k 2 * (N-1)<\/code> kontrol yap\u0131l\u0131r. Toplamda N<\/code> aday oldu\u011fu i\u00e7in, algoritman\u0131n toplam zaman karma\u015f\u0131kl\u0131\u011f\u0131 yakla\u015f\u0131k olarak N * 2 * (N-1)<\/code> olur. Bu da matematiksel olarak O(N^2)<\/code> olarak ifade edilir.<\/p>\nO(N^2)<\/code> zaman karma\u015f\u0131kl\u0131\u011f\u0131, N<\/code> de\u011feri b\u00fcy\u00fcd\u00fck\u00e7e performans\u0131n \u00e7ok h\u0131zl\u0131 bir \u015fekilde k\u00f6t\u00fcle\u015fece\u011fi anlam\u0131na gelir. \u00d6rne\u011fin, 100 ki\u015filik bir grupta 10.000’e yak\u0131n i\u015flem gerekirken, 10.000 ki\u015filik bir grupta 100.000.000’a yak\u0131n i\u015flem gerekebilir. Bu durum, \u00f6zellikle b\u00fcy\u00fck veri k\u00fcmeleriyle \u00e7al\u0131\u015f\u0131rken kabul edilemez bir yava\u015fl\u0131\u011fa yol a\u00e7abilir. Bu nedenle, daha verimli bir \u00e7\u00f6z\u00fcme ihtiyac\u0131m\u0131z var. \u015eimdi, bu k\u0131s\u0131tlamalar\u0131 a\u015fmak ve daha h\u0131zl\u0131 bir yol bulmak i\u00e7in nas\u0131l d\u00fc\u015f\u00fcnebilece\u011fimize odaklanal\u0131m.<\/p>\nVerimli Bir \u00c7\u00f6z\u00fcme Do\u011fru: \u0130pu\u00e7lar\u0131 ve K\u0131s\u0131tlamalar<\/h2>\n
O(N^2)<\/code> zaman karma\u015f\u0131kl\u0131\u011f\u0131na sahip oldu\u011funu g\u00f6rd\u00fck. Bu, k\u00fc\u00e7\u00fck gruplar i\u00e7in kabul edilebilir olsa da, b\u00fcy\u00fck sosyal a\u011flar veya kurumsal hiyerar\u015filer gibi N<\/code> de\u011ferinin binlere, hatta milyonlara ula\u015ft\u0131\u011f\u0131 senaryolarda pratik olmaktan uzakt\u0131r. Bir algoritman\u0131n verimlili\u011fi, genellikle b\u00fcy\u00fck \u00f6l\u00e7ekli sistemlerdeki performans\u0131 belirleyen kritik bir fakt\u00f6rd\u00fcr. Bu y\u00fczden, \u00dcnl\u00fc Problemi i\u00e7in daha h\u0131zl\u0131, yani O(N)<\/code> zaman karma\u015f\u0131kl\u0131\u011f\u0131na sahip bir \u00e7\u00f6z\u00fcm bulmak b\u00fcy\u00fck \u00f6nem ta\u015f\u0131r.<\/p>\nO(N^2)<\/code>‘den O(N)<\/code>‘ye ge\u00e7i\u015f yapabilmek i\u00e7in, her bir ki\u015fi i\u00e7in t\u00fcm olas\u0131 tan\u0131\u015f\u0131kl\u0131k ili\u015fkilerini tekrar tekrar kontrol etmek yerine, her bir ili\u015fkiyi veya sorguyu daha ak\u0131ll\u0131ca kullanmam\u0131z gerekir. Temel fikir, bir sorgunun sonucundan yola \u00e7\u0131karak potansiyel adaylar\u0131 elemek ve b\u00f6ylece arama alan\u0131n\u0131 daraltmakt\u0131r. Her bir “kim kimi tan\u0131yor?” sorusunun bize yeni bir bilgi vermesi ve bu bilginin bir veya birden fazla ki\u015fiyi \u00fcnl\u00fc aday\u0131 olmaktan \u00e7\u0131karmas\u0131 gerekir. Bu, bir eleme s\u00fcreci gibi d\u00fc\u015f\u00fcn\u00fclebilir.<\/p>\n\n
tan\u0131yor(A, B)<\/code> do\u011fru (A, B’yi tan\u0131yor): Bu durumda, A kesinlikle \u00fcnl\u00fc olamaz. \u00c7\u00fcnk\u00fc \u00fcnl\u00fcler kimseyi tan\u0131maz. Ayr\u0131ca, B’nin \u00fcnl\u00fc olabilme potansiyeli devam eder.<\/li>\ntan\u0131yor(A, B)<\/code> yanl\u0131\u015f (A, B’yi tan\u0131m\u0131yor): Bu durumda, B kesinlikle \u00fcnl\u00fc olamaz. \u00c7\u00fcnk\u00fc \u00fcnl\u00fcy\u00fc herkes tan\u0131mal\u0131d\u0131r; e\u011fer A, B’yi tan\u0131m\u0131yorsa, B \u00fcnl\u00fc olamaz. A’n\u0131n \u00fcnl\u00fc olabilme potansiyeli devam eder.<\/li>\ntan\u0131yor(B, A)<\/code> do\u011fru (B, A’y\u0131 tan\u0131yor): Bu durumda, B kesinlikle \u00fcnl\u00fc olamaz. Ayn\u0131 mant\u0131kla, A’n\u0131n \u00fcnl\u00fc olabilme potansiyeli devam eder.<\/li>\ntan\u0131yor(B, A)<\/code> yanl\u0131\u015f (B, A’y\u0131 tan\u0131m\u0131yor): Bu durumda, A kesinlikle \u00fcnl\u00fc olamaz. Ayn\u0131 mant\u0131kla, B’nin \u00fcnl\u00fc olabilme potansiyeli devam eder.<\/li>\n<\/ol>\nN<\/code> ki\u015fi varsa, en fazla N-1<\/code> sorgu ile potansiyel \u00fcnl\u00fc aday\u0131n\u0131 bire indirebiliriz. Bu, bizi do\u011frudan O(N)<\/code> zaman karma\u015f\u0131kl\u0131\u011f\u0131na g\u00f6t\u00fcrecek bir stratejinin kap\u0131s\u0131n\u0131 aralar. Bir sonraki b\u00f6l\u00fcmde, bu eleme mant\u0131\u011f\u0131n\u0131 kullanarak nas\u0131l tek ge\u00e7i\u015fli (single-pass) bir algoritma tasarlayabilece\u011fimizi g\u00f6rece\u011fiz.<\/p>\nTek Ge\u00e7i\u015fli Algoritma: \u00dcnl\u00fcy\u00fc O(n) S\u00fcrede Bulmak<\/h3>\n
O(N^2)<\/code> kaba kuvvet \u00e7\u00f6z\u00fcm\u00fcn\u00fcn aksine, \u00dcnl\u00fc Problemi i\u00e7in O(N)<\/code> zaman karma\u015f\u0131kl\u0131\u011f\u0131na sahip \u00e7ok daha verimli bir algoritma mevcuttur. Bu algoritma, yukar\u0131da bahsetti\u011fimiz eleme mant\u0131\u011f\u0131n\u0131 kullanarak, her bir sorguda en az bir aday\u0131 eleyerek \u00e7al\u0131\u015f\u0131r. Bu sayede, potansiyel \u00fcnl\u00fc aday\u0131 say\u0131s\u0131n\u0131 h\u0131zla azalt\u0131r\u0131z. Bu y\u00f6ntemin en yayg\u0131n uygulamalar\u0131ndan biri, bir y\u0131\u011f\u0131n (stack) veya iki i\u015faret\u00e7i (two-pointer) yakla\u015f\u0131m\u0131 kullanmakt\u0131r.<\/p>\nY\u0131\u011f\u0131n (Stack) Tabanl\u0131 Yakla\u015f\u0131m<\/h4>\n
\n
tan\u0131yor(A, B)<\/code> sorgusunu yapar\u0131z:\n\n
tan\u0131yor(A, B) == True<\/code>): A kesinlikle \u00fcnl\u00fc olamaz. B hala \u00fcnl\u00fc aday\u0131 olabilir, bu y\u00fczden B’yi y\u0131\u011f\u0131na geri ekleriz.<\/li>\ntan\u0131yor(A, B) == False<\/code>): B kesinlikle \u00fcnl\u00fc olamaz. A hala \u00fcnl\u00fc aday\u0131 olabilir, bu y\u00fczden A’y\u0131 y\u0131\u011f\u0131na geri ekleriz.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\naday<\/code>) bulduktan sonra, bu ki\u015finin ger\u00e7ekten \u00fcnl\u00fc olup olmad\u0131\u011f\u0131n\u0131 son bir kontrolle do\u011frulamam\u0131z gerekir. Bu do\u011frulama, iki ko\u015fulun da (kimseyi tan\u0131mamas\u0131 ve herkesin onu tan\u0131mas\u0131) sa\u011flan\u0131p sa\u011flanmad\u0131\u011f\u0131n\u0131 kontrol etmeyi i\u00e7erir. Bu son do\u011frulama ad\u0131m\u0131 da O(N)<\/code> zaman al\u0131r.<\/p>\n\n\/\/ Y\u0131\u011f\u0131n Tabanl\u0131 O(N) \u00c7\u00f6z\u00fcm \u0130\u00e7in Pseudocode\nfonksiyon findCelebrityOptimized(N, tan\u0131yor):\n stack = bo\u015f bir y\u0131\u011f\u0131n\n her ki\u015fi 'i' (0'dan N-1'e kadar) i\u00e7in:\n stack.push(i) \/\/ T\u00fcm ki\u015fileri y\u0131\u011f\u0131na ekle\n\n while stack.size() > 1:\n A = stack.pop()\n B = stack.pop()\n\n e\u011fer tan\u0131yor(A, B): \/\/ A, B'yi tan\u0131yorsa, A \u00fcnl\u00fc olamaz\n stack.push(B)\n else: \/\/ A, B'yi tan\u0131m\u0131yorsa, B \u00fcnl\u00fc olamaz\n stack.push(A)\n \n e\u011fer stack.is_empty():\n d\u00f6n -1 \/\/ \u00dcnl\u00fc yok\n\n potansiyel_\u00fcnl\u00fc = stack.pop()\n\n \/\/ Son do\u011frulama ad\u0131m\u0131: potansiyel_\u00fcnl\u00fc ger\u00e7ekten \u00fcnl\u00fc m\u00fc?\n \/\/ Ko\u015ful 1: potansiyel_\u00fcnl\u00fc kimseyi tan\u0131m\u0131yor mu?\n her ki\u015fi 'i' (0'dan N-1'e kadar) i\u00e7in:\n e\u011fer i != potansiyel_\u00fcnl\u00fc VE tan\u0131yor(potansiyel_\u00fcnl\u00fc, i) == True:\n d\u00f6n -1 \/\/ \u00dcnl\u00fc de\u011fil, \u00e7\u00fcnk\u00fc birini tan\u0131yor\n\n \/\/ Ko\u015ful 2: Herkes potansiyel_\u00fcnl\u00fc'y\u00fc tan\u0131yor mu?\n her ki\u015fi 'i' (0'dan N-1'e kadar) i\u00e7in:\n e\u011fer i != potansiyel_\u00fcnl\u00fc VE tan\u0131yor(i, potansiyel_\u00fcnl\u00fc) == False:\n d\u00f6n -1 \/\/ \u00dcnl\u00fc de\u011fil, \u00e7\u00fcnk\u00fc biri onu tan\u0131m\u0131yor\n \n d\u00f6n potansiyel_\u00fcnl\u00fc \/\/ \u00dcnl\u00fc bulundu\n <\/code><\/pre>\n<\/p><\/div>\nO(N)<\/code>‘dir. Son do\u011frulama ad\u0131m\u0131 da iki ayr\u0131 O(N)<\/code> d\u00f6ng\u00fc i\u00e7erir. Dolay\u0131s\u0131yla, toplam zaman karma\u015f\u0131kl\u0131\u011f\u0131 O(N) + O(N) + O(N) = O(N)<\/code> olur. Bu, N<\/code> de\u011feri ne kadar b\u00fcy\u00fck olursa olsun, algoritman\u0131n performans\u0131n\u0131n do\u011frusal olarak artaca\u011f\u0131 anlam\u0131na gelir; bu da onu b\u00fcy\u00fck veri k\u00fcmeleri i\u00e7in son derece verimli k\u0131lar.<\/p>\n\u0130ki \u0130\u015faret\u00e7i (Two-Pointer) Yakla\u015f\u0131m\u0131<\/h4>\n
O(N)<\/code> \u00e7\u00f6z\u00fcme ula\u015fabiliriz. Bu yakla\u015f\u0131mda, iki i\u015faret\u00e7i (left<\/code> ve right<\/code>) kullan\u0131r\u0131z. left<\/code> 0’dan ba\u015flarken, right<\/code> N-1<\/code>‘den ba\u015flar. \u0130\u015faret\u00e7iler birbirini ge\u00e7ene kadar a\u015fa\u011f\u0131daki ad\u0131mlar\u0131 tekrarlar\u0131z:<\/p>\n\n
tan\u0131yor(left, right)<\/code> sorgusunu yapar\u0131z:\n\n
left<\/code>, right<\/code>‘\u0131 tan\u0131yorsa: left<\/code> \u00fcnl\u00fc olamaz (\u00e7\u00fcnk\u00fc birini tan\u0131yor). left<\/code>‘i bir art\u0131r\u0131r\u0131z.<\/li>\nleft<\/code>, right<\/code>‘\u0131 tan\u0131m\u0131yorsa: right<\/code> \u00fcnl\u00fc olamaz (\u00e7\u00fcnk\u00fc left<\/code> onu tan\u0131m\u0131yor). right<\/code>‘\u0131 bir azalt\u0131r\u0131z.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\nleft<\/code> i\u015faret\u00e7isinin g\u00f6sterdi\u011fi ki\u015fi potansiyel \u00fcnl\u00fc aday\u0131m\u0131zd\u0131r. (Bu durumda left<\/code> ve right<\/code> ayn\u0131 ki\u015fiyi g\u00f6sterir veya left<\/code>, right<\/code>‘tan bir b\u00fcy\u00fck olur, bu da left<\/code>‘in son potansiyel aday oldu\u011funu g\u00f6sterir.) Sonras\u0131nda, y\u0131\u011f\u0131n tabanl\u0131 yakla\u015f\u0131mda oldu\u011fu gibi, bu potansiyel aday\u0131n ger\u00e7ekten \u00fcnl\u00fc olup olmad\u0131\u011f\u0131n\u0131 O(N)<\/code> zamanda do\u011frulamam\u0131z gerekir.<\/p>\n\n\/\/ \u0130ki \u0130\u015faret\u00e7i Tabanl\u0131 O(N) \u00c7\u00f6z\u00fcm \u0130\u00e7in Pseudocode\nfonksiyon findCelebrityTwoPointers(N, tan\u0131yor):\n left = 0\n right = N - 1\n\n while left < right:\n e\u011fer tan\u0131yor(left, right): \/\/ left, right'\u0131 tan\u0131yorsa, left \u00fcnl\u00fc olamaz\n left = left + 1\n else: \/\/ left, right'\u0131 tan\u0131m\u0131yorsa, right \u00fcnl\u00fc olamaz\n right = right - 1\n \n potansiyel_\u00fcnl\u00fc = left \/\/ D\u00f6ng\u00fc bitti\u011finde left, potansiyel \u00fcnl\u00fcy\u00fc g\u00f6sterir\n\n \/\/ Son do\u011frulama ad\u0131m\u0131 (y\u0131\u011f\u0131n yakla\u015f\u0131m\u0131yla ayn\u0131)\n \/\/ Ko\u015ful 1: potansiyel_\u00fcnl\u00fc kimseyi tan\u0131m\u0131yor mu?\n her ki\u015fi 'i' (0'dan N-1'e kadar) i\u00e7in:\n e\u011fer i != potansiyel_\u00fcnl\u00fc VE tan\u0131yor(potansiyel_\u00fcnl\u00fc, i) == True:\n d\u00f6n -1\n\n \/\/ Ko\u015ful 2: Herkes potansiyel_\u00fcnl\u00fc'y\u00fc tan\u0131yor mu?\n her ki\u015fi 'i' (0'dan N-1'e kadar) i\u00e7in:\n e\u011fer i != potansiyel_\u00fcnl\u00fc VE tan\u0131yor(i, potansiyel_\u00fcnl\u00fc) == False:\n d\u00f6n -1\n \n d\u00f6n potansiyel_\u00fcnl\u00fc\n <\/code><\/pre>\n<\/p><\/div>\nO(N)<\/code> \u00e7\u00f6z\u00fcm\u00fc de, kaba kuvvet yakla\u015f\u0131m\u0131na g\u00f6re \u00e7ok daha \u00fcst\u00fcnd\u00fcr ve b\u00fcy\u00fck \u00f6l\u00e7ekli uygulamalar i\u00e7in vazge\u00e7ilmezdir. Bu \u00e7\u00f6z\u00fcmler, algoritmik d\u00fc\u015f\u00fcnme ve eleme stratejilerinin g\u00fcc\u00fcn\u00fc a\u00e7\u0131k\u00e7a ortaya koymaktad\u0131r.<\/p>\n\u00dcnl\u00fc Problemi Sadece Partiler \u0130\u00e7in mi? Ger\u00e7ek D\u00fcnya Senaryolar\u0131<\/h2>\n
1. Sosyal A\u011f Analizi ve G\u00fcven Mekanizmalar\u0131<\/h4>\n
2. Ba\u011f\u0131ml\u0131l\u0131k \u00c7\u00f6z\u00fcmlemesi (Dependency Resolution)<\/h4>\n
3. G\u00fcvenlik ve Yetkilendirme Sistemleri<\/h4>\n
4. Veritaban\u0131 Optimizasyonu<\/h4>\n
K\u00f6\u015fe Durumlar ve Optimizasyon \u0130pu\u00e7lar\u0131<\/h3>\n
1. \u00dcnl\u00fc Olmamas\u0131 Durumu<\/h4>\n
O(N)<\/code> \u00e7\u00f6z\u00fcmlerimiz, bu durumu ba\u015far\u0131yla ele al\u0131r. Y\u0131\u011f\u0131n tabanl\u0131 veya iki i\u015faret\u00e7i tabanl\u0131 algoritmalar, e\u011fer bir \u00fcnl\u00fc yoksa, son do\u011frulama ad\u0131m\u0131nda (kimseyi tan\u0131m\u0131yor mu? herkes onu tan\u0131yor mu?) ba\u015far\u0131s\u0131z olacak ve -1<\/code> (veya \u00fcnl\u00fc yok anlam\u0131nda ba\u015fka bir de\u011fer) d\u00f6nd\u00fcrecektir. Bu, algoritman\u0131n hem \u00fcnl\u00fc buldu\u011funda hem de bulamad\u0131\u011f\u0131nda do\u011fru \u00e7al\u0131\u015ft\u0131\u011f\u0131n\u0131 g\u00f6sterir.<\/p>\n2. Birden Fazla \u00dcnl\u00fc Olabilir mi?<\/h4>\n
\n
3. Bo\u015f Grup veya Tek Ki\u015filik Grup<\/h4>\n
N=0<\/code>), \u00fcnl\u00fc yoktur. E\u011fer grupta sadece bir ki\u015fi varsa (N=1<\/code>), o ki\u015fi otomatik olarak \u00fcnl\u00fcd\u00fcr (\u00e7\u00fcnk\u00fc kimseyi tan\u0131mas\u0131 veya kimsenin onu tan\u0131mas\u0131 gibi bir durum s\u00f6z konusu de\u011fildir). Algoritmalar\u0131m\u0131z\u0131n bu durumlar\u0131 da do\u011fru \u015fekilde ele ald\u0131\u011f\u0131ndan emin olmal\u0131y\u0131z. Genellikle N=0<\/code> i\u00e7in -1<\/code>, N=1<\/code> i\u00e7in 0<\/code> (tek ki\u015finin indeksi) d\u00f6nd\u00fcr\u00fcl\u00fcr.<\/p>\n4. Optimizasyon \u0130pu\u00e7lar\u0131: Sorgu Fonksiyonunun Maliyeti<\/h4>\n
O(N)<\/code> \u00e7\u00f6z\u00fcmlerimiz, tan\u0131yor(i, j)<\/code> fonksiyonunun sabit zamanda (O(1)<\/code>) \u00e7al\u0131\u015ft\u0131\u011f\u0131n\u0131 varsayar. Bu genellikle, tan\u0131\u015f\u0131kl\u0131k matrisinin bellekte do\u011frudan eri\u015filebilir olmas\u0131 durumunda ge\u00e7erlidir. Ancak, e\u011fer tan\u0131yor<\/code> fonksiyonu bir veritaban\u0131 sorgusu yap\u0131yor veya bir a\u011f iste\u011fi g\u00f6nderiyorsa, bu fonksiyonun maliyeti sabit zaman olmayabilir. B\u00f6yle durumlarda, algoritman\u0131n toplam zaman karma\u015f\u0131kl\u0131\u011f\u0131 O(N * M)<\/code> olabilir, burada M<\/code> sorgu fonksiyonunun maliyetidir. Bu gibi senaryolarda, sorgu say\u0131s\u0131n\u0131 minimize etmek i\u00e7in \u00f6nbellekleme (caching) mekanizmalar\u0131 d\u00fc\u015f\u00fcn\u00fclebilir.<\/p>\n\u00dcnl\u00fc Problemi: Algoritmik D\u00fc\u015f\u00fcnmenin G\u00fcc\u00fc<\/h2>\n
O(N)<\/code> zaman karma\u015f\u0131kl\u0131\u011f\u0131na sahip optimize edilmi\u015f \u00e7\u00f6z\u00fcmlere nas\u0131l ula\u015ft\u0131\u011f\u0131m\u0131z\u0131 ad\u0131m ad\u0131m inceledik. G\u00f6rd\u00fc\u011f\u00fcm\u00fcz gibi, basit bir \"kim kimi tan\u0131yor?\" sorusundan yola \u00e7\u0131karak, eleme stratejileri ve ak\u0131ll\u0131 veri yap\u0131lar\u0131 (y\u0131\u011f\u0131n veya iki i\u015faret\u00e7i) kullanarak algoritmik verimlili\u011fi nas\u0131l katlayarak art\u0131rabilece\u011fimizi ke\u015ffettik. O(N^2)<\/code>'den O(N)<\/code>'ye ge\u00e7i\u015f, sadece teorik bir iyile\u015ftirme de\u011fil, ayn\u0131 zamanda b\u00fcy\u00fck \u00f6l\u00e7ekli sistemlerde performans ve kaynak kullan\u0131m\u0131 a\u00e7\u0131s\u0131ndan muazzam bir fark yaratan pratik bir gerekliliktir.<\/p>\nS\u0131k\u00e7a Sorulan Sorular<\/h3>\n
\n
O(N^2)<\/code> ve O(N)<\/code> \u00e7\u00f6z\u00fcmler aras\u0131ndaki temel fark nedir?<\/strong><\/p>\nO(N^2)<\/code> (kaba kuvvet) \u00e7\u00f6z\u00fcm\u00fc, her bir ki\u015fiyi potansiyel \u00fcnl\u00fc olarak kontrol etmek i\u00e7in i\u00e7 i\u00e7e d\u00f6ng\u00fcler kullan\u0131r ve bu da N<\/code> ki\u015fi i\u00e7in yakla\u015f\u0131k N*N<\/code> i\u015flem gerektirir. O(N)<\/code> \u00e7\u00f6z\u00fcm\u00fc ise (y\u0131\u011f\u0131n veya iki i\u015faret\u00e7i tabanl\u0131), her sorguda en az bir aday\u0131 eleyerek ve toplamda yakla\u015f\u0131k N<\/code> i\u015flem yaparak \u00fcnl\u00fcy\u00fc bulur. B\u00fcy\u00fck veri k\u00fcmelerinde O(N)<\/code> \u00e7ok daha h\u0131zl\u0131d\u0131r.<\/p>\n<\/li>\ntan\u0131yor(i, j)<\/code> fonksiyonunun maliyeti ne anlama gelir?<\/strong><\/p>\ntan\u0131yor(i, j)<\/code> fonksiyonu, i<\/code> ki\u015finin j<\/code> ki\u015fiyi tan\u0131y\u0131p tan\u0131mad\u0131\u011f\u0131n\u0131 kontrol eden bir soyutlamad\u0131r. Genellikle bu fonksiyonun sabit zamanda (O(1)<\/code>) \u00e7al\u0131\u015ft\u0131\u011f\u0131 varsay\u0131l\u0131r (\u00f6rne\u011fin bir matris sorgusu). Ancak e\u011fer bu fonksiyon bir veritaban\u0131 \u00e7a\u011fr\u0131s\u0131 veya a\u011f iste\u011fi gibi maliyetli bir i\u015flem i\u00e7eriyorsa, algoritman\u0131n ger\u00e7ek performans\u0131 bu maliyetten etkilenebilir.<\/p>\n<\/li>\nO(N)<\/code> \u00e7\u00f6z\u00fcm\u00fc i\u00e7in y\u0131\u011f\u0131n (stack) veya iki i\u015faret\u00e7i (two-pointer) gibi basit veri yap\u0131lar\u0131 ve teknikler yeterlidir.<\/p>\n<\/li>\n<\/ul>\n